One thought I’ve never had: “I wish I hadn’t been so much time thinking about Big O notation, power laws, and orders of magnitudes”
Big O Notation – Explained as easily as possible
61–70 of 168 posts
Re: Big O Notation – Explained as easily as possible
#62That in _no_ way explained big-O notation. It explained the basics of counting things to do with algorithms. Which is kind of fine, really. But why bother saying it's going to explain big-O?
Re: Big O Notation – Explained as easily as possible
#63If you are the kind of person that want to read an article titled "explained as easily as possible", I think you should just avoid saying the phrase "big oh" but instead talk about algorithm runtime more informally, like "quicksort has a worst case quadratic but average case n log n runtime". The risk is otherwise you will shoot yourself in the foot, maybe during an interview or other situation, as Big O is just one…
>Analysis of algorithms is more difficult than it appears. If you implement an algorithm in a high level language like Python you may get much worse runtime than you thought because some inner loop does arithmetic with bignum-style performance instead of hardware integer performance, for example. In such case you could talk of big-omega (your analysis is bounded-below instead of bounded-above, asymptotically).
Of course, that's why Big O says one thing, Compiler, CPU and Caches may say the other.
Re: Big O Notation – Explained as easily as possible
#64Much better explained than in my computer science lectures! Nice simple examples.
It's such an important topic to grasp too if you're going to end up working with software!
Re: Big O Notation – Explained as easily as possible
#65Re: Big O Notation – Explained as easily as possible
#66If you are the kind of person that want to read an article titled "explained as easily as possible", I think you should just avoid saying the phrase "big oh" but instead talk about algorithm runtime more informally, like "quicksort has a worst case quadratic but average case n log n runtime". The risk is otherwise you will shoot yourself in the foot, maybe during an interview or other situation, as Big O is just one…
> If you implement an algorithm in a high level language like Python you may get much worse runtime than you thought because some inner loop does arithmetic with bignum-style performance instead of hardware integer performance If a language/library can change the dominant asymptotic term of an algorithm like that, instead of just the constant factor, that is a problem. Does that really happen with python or is this e…
The language doesn't matter, nor even it's high vs low class.
You can write a short function in any language that looks O(1) if you only look at the surface or high level of it. Even assembly. Meanwhile in the middle of that routine is a single call to another function or macro which may be 0(1) or O(n!).
Python was just an example.
Re: Big O Notation – Explained as easily as possible
#67Not a bad intro and appreciate the intention on keeping it short and simple, but personally for me I think Grokking Algorithms has the best beginner explanations of Big O and basic algorithms / data structures. If I had to share resources with a learner, I'd suggest Grokking as an item to go deeper on after reading this article.
Re: Big O Notation – Explained as easily as possible
#68[deleted]
Re: Big O Notation – Explained as easily as possible
#69It's great to have a handle on big O but funny I've seen people index to it too much. An algorithm can look "really bad" from Big-O point of view and still be really good if: it's applied to a small enough input, or it's implemented very efficiently.
> it's applied to a small enough input The whole point of big-O notation is to analyze algorithms as they're applied to input of size `n` larger than some `n_0`. Of course it's not useful for small inputs - it's explicitly about large inputs. > it's implemented very efficiently On large inputs, it's very hard see how, say, a linear algorithm with a quadratic algorithm regardless of how "efficiently" it's implemented.…
Yeah we are talking about the same thing. I agree that what you are saying is deeply connected to value of Big O. I am just pointing out that people sometimes forget to consider these things.
Re: Big O Notation – Explained as easily as possible
#70Earlier quoted context omitted.
I hear you. Whether I like it or not, by now big o notation has fallen into the category of "folklore" that working engineers use and abuse informally without being very precise about it. It's like the "proof by engineers induction": if some statement P(n) is true for P(0), P(1) and P(2), then P(n) is true for all n \in Z. :-) Similarly if an engineer states that algorithm has a runtime of O(f(n)) that should probabl…
There can be appropriate levels of imprecision. Arguably all communication necessarily requires that. This is only a problem if it leads to an unnoticed miscommunication. For example, I suspect most of the time when an engineers refers to an algorithm as being in O(n^2) they intend to preclude the possibility that the algorithm is not in O(n).
Usually "average" or worst case" O(n^2) means it's really big O, while "best case" or "always" O(n log n) means big Theta.