Big O Notation – Explained as easily as possible
thatcomputerscientist.com
Big O Notation – Explained as easily as possible
1–10 of 168 posts
Re: Big O Notation – Explained as easily as possible
#2lkjhlkjhlk
Re: Big O Notation – Explained as easily as possible
#3https://nedbatchelder.com/text/bigo/bigo.html is also a good intro read.
Re: Big O Notation – Explained as easily as possible
#4Just read a book on algorithms. They are timeless, unlike APIs, so it's worth the effort to study them.
Re: Big O Notation – Explained as easily as possible
#5Count the number of nested loops. If one of the loops does splitting (like binary search) it’s a O(log n) as opposed to O(n).
That’s literally all there is to it.
Re: Big O Notation – Explained as easily as possible
#6Count the number of nested loops. If one of the loops does splitting (like binary search) it’s a O(log n) as opposed to O(n). That’s literally all there is to it.
What if there are recursive function calls?
Re: Big O Notation – Explained as easily as possible
#7If 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 out of many members in a family of notations that has a very specific mathematical definition, other common ones being small-o and big-theta.
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).
Re: Big O Notation – Explained as easily as possible
#8Re: Big O Notation – Explained as easily as possible
#9Re: Big O Notation – Explained as easily as possible
#10If 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…
It is still a useful conceptual framework. Maybe this sparks someone’s interest. Agree it is much harder than it appears :)