A beginner's guide to Big O notation (2009)

https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

by g4k • 10 years ago

312 65 10 years ago

minikites3• 10 years ago

The best layman's example of O(log N) I've heard is finding a name in the phone book. You open it around the middle, select which half gets you closer, and repeat. It's then easy to "get" why it's not a big deal if it's a huge phone book versus a tiny phone book.

noobiemcfoob2• 10 years ago

That seems more like a layman's explanation of a binary search than O(log N). Binary search just happens to be O(log N)

minikites3• 10 years ago

I'm not sure how drawing that distinction helps a layman.

Jtsummers3• 10 years ago

Binary search is an example of a O(log N) algorithm, as OP said. Having tangible examples is great for explaining algorithmic complexity to people.

One I've used is sorting with a deck of cards. Take a single suit, A-K, and have people sort it using bubble or insertion or other sorts. It's only 13 cards, but the difference even between some of the O(n^2) algorithms becomes obvious when swapping is postponed until the latest stage versus earliest.

Then you can also demonstrate radix sort. One of the most underrated sorting algorithms, in my opinion. A lot of people focus on the (potentially) large constant. But it can be appropriate, or may be reduced depending on your use-case. And it's a fantastic sort when you can't give a neat numeric quality for sorting and have to sort over multiple dimensions. Again with cards, you can do two passes. One with buckets by value, and one with buckets by suit. After the second, you collect each of the 4 stacks and the deck is sorted.

Cards, phone books, recipes, these are things that most people encounter (ok, maybe not phone books anymore), in their lives. They offer great aids to demonstrating CS concepts to either new students or people who have only a passing curiosity (or none but they shouldn't have asked :P).

dominotw2• 10 years ago

Thats not a good example for Big O because number of operations computes exactly to logN in worst case.

Try with mergesort and see how it ends being nlogn

george_soros• 10 years ago

Isn't O(log n) just an upper bound limit ? So isn't it more correct to say, that in worst case the number of steps are < O(log n) ?

stevewilhelm• 10 years ago

A phone book? How is Amazon's Kindle App O(log N)? ;-)

hnkain2• 10 years ago

A phone book search does O(log N) string comparisons, but its running time is not O(log N) unless you consider all string comparisons to take a constant amount of time. Because for the names in the phone book to be distinct, the strings have to be about log N in size, so each string comparison costs O(log N) in the worst case. So the cost of phone book search is O((log N)^2).

I've skipped some details here: string comparisons can finish early, and maybe N should be the size of the phone book rather than the number of names in the phone book -- but even if you consider these factors, the runtime complexity is still more than O(log N).

vvanders4• 10 years ago

O(N) describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set.

Argh, I hate this every time I see Big O notation covered.

Big O != performance. If you have an O(N) algorithm that walks the data set in the order that it's laid out in memory(assuming contiguous data) it will beat your O(NlogN) and sometimes even O(logN).

[edit]meant to omit nlogn, that's what I get for any early morning rant pre-coffee.

Radix Sort is the classic example I always bring up. On machine word size keys, with a separate pointer look-up table(to get final value) it will beat QSort, MergeSort and all the other NlogN sorts by 10-50x. This includes having to walk the data 3-4 times depending on how you want to split the radix to line up with cache sizes.

Friends don't let Friends use Big O to describe absolute performance.

dominotw2• 10 years ago

By one estimate, the health care costs of obesity are responsible for nearly 21 percent of total health care spending in the U.S.

BigO has nothing to do with performance even though that what we most use it for.

Its simply a classification of growth characteristics, relationship between two functions.

castratikron• 10 years ago

Of course an O(N) method will beat an O(NlgN) method, because O(N) < O(NlgN).

Radix sort is a linear time sort because the hardware (random access memory) is built to allow constant-time lookup of memory. Radix sort wouldn't be linear time on a sequential access memory system, like tape, but merge sort would still be O(NlgN) on such a system.

hnkain2• 10 years ago

It doesn't invalidate what you say, but you're assuming there's a bounded number of different values in the array -- 2^k where k is your word size.

Under this assumption, a correctly implemented quicksort also runs in O(N) time.

decebalus1• 10 years ago

If you have an O(N) algorithm that walks the data set in the order that it's laid out in memory(assuming contiguous data) it will beat your O(NlogN)

Not sure what you're trying to say with this particular statement. Of course it will. NLogN grows way faster than N.

And Radix sort is of course drastically faster than comparison sorts if the word size is smaller than logN regardless of the particularities of the implementation.

People don't and shouldn't use big O to describe absolute performance but it's a great place to start and you can't reach the level of implementation details performance tuning if you can't understand or formalize the basics.

But you do have a point overall.

In practice, performance may be different. Big O assumes a particular 'virtual machine' with a particular word size and a particular time it takes to execute an instruction.

vvanders4• 10 years ago

Yeah, meant to omit NlogN there, I blame it on lack of coffee.

My meta point is the constant factors that Big O throws out usually end up dominating real-world performance.

Rhapso• 10 years ago

In big-O senses Radix sort is one of those more persistent misconceptions. At scale Radix sort has to be nlog(n) because you should really consider the possibility all your numbers are unique.

This does not even start on the reality that memory access really is O(n^(1/3)), addition is O(n) and a lot of other things we assume are O(1) are not.

bojank• 10 years ago

When talking about theory, I have two points: - First: O(N) < O(N log N), so your example isn't good - Second: Your description of Radix sort is actually O(N), and the standard sorting algorithms are O(N log N), so it again isn't a surprise, theoretically speaking...

The thing that Big-O knowingly hides is the constant factor. For example, some algorithms are 2N and some are 1000N. For large enough N, this may not matter, but for any reasonably sized N, it does.

In practice, of course that Big-O is not sufficient to describe absolute algorithm performance, as it depends on so many factors such as implementation, computer architecture, relative size of data, etc. But, when looking at an algorithm and knowing its Big-O complexity can often be a useful input to your decision on whether to use it. So I disagree with this Big-O bashing...

umanwizard4• 10 years ago

The statement you quoted is correct. It doesn't say "O(log(N)) algorithms are faster than O(N) algorithms." It says performance of a particular algorithm degrades linearly as data set grows, if that algorithm is O(N). Which is true. (asymptotically)

vvanders4• 10 years ago

I was nitpicking the performance part of the statement. N does scale linearly.

The point I was trying(and failed) to drive home is that it matters how you walk your N not just what the N is.

If you've got to do a pointer indirection for each N rather than a linear read that can end up dominating the non-constant factors in a lot of cases.

TillE• 10 years ago

You're overlooking the word "grow".

There's nothing wrong with that sentence. No absolutes.

mattlutze• 10 years ago

Looks like someone finally got it to the front page:

https://news.ycombinator.com/from?site=rob-bell.net

Practicality• 10 years ago

It's all about putting the year on there.

emodendroket2• 10 years ago

Looks like the asymptotic complexity of getting this article to the frontpage is pretty high.

Lxr3• 10 years ago

O(N) describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set

Nitpick, but this is technically wrong. There needs to be a "no faster than" somewhere in there. Merge sort is, for example, included in O(2^n) by the actual definition of big O (vs big theta, which is defined as a tight bound). So there exist algorithms that are O(N) that don't grow linearly.

f(x) is O(g(x)) just means there is some constant K such that f(x) <= Kg(x) for all x beyond some value. This has nothing to do with 'worst case performance'.

Jtsummers3• 10 years ago

Do you mean O(n^2)? Because merge sort certainly won't be exponential.

Lxr3• 10 years ago

No, I mean O(2^n). O(2^n) includes everything that grows slower than 2^n as well. It is no relation to the worst case performance of merge sort, just a clarification on the definition of Big O.

umanwizard4• 10 years ago

You'll be a lot happier if you mentally replace O(n) with Theta(n) every time you see it, rather than feeling the need to nitpick when you know that that's what people mean when they say O(n), 99% of the time.

marcosdumay• 10 years ago

Problem is that Theta(n) is an almost useless notation.

Thus, most times people say O(n) on practice[1], they mean O(n). But most times people define O(n), they cite the Theta(n) definition.

It isn't hard to put an "up to", "no more than" or "or less" at the definition, and it does not make it threatening or hard to read.

[1] There's probably a small corner in Hell reserved for people that mean O(n) on average but refuse both to say that qualifier and care about what data distribution created that average.

nayuki2• 10 years ago

The article is mostly good, but I have one nitpick.

An example of an O(2^N) function is the recursive calculation of Fibonacci numbers

No, the naive recursive evaluation of the Fibonacci sequence has complexity O(1.618^N) (or just O(Fib(n)). It is unequal to O(2^N) because the base of the power is different.

Scea913• 10 years ago

Technically 1.618^N is still O(2^N) but I agree with your point.

mantasm2• 10 years ago

I was about to correct you until I realized you used big-O instead of big-theta notation.

Informally we tend to use big-O to mean big-theta which only adds to the confusion.

mattb314• 10 years ago

To be fair, as Lxr points out below, big O notation is an upper bound on the growth rate of a function, and since 2^N grows faster (asymptotically) than (1.618...)^N, O(Fib(N)) <= O(1.618...^N) <= O(2^N) (with some abuse of notation), and the article is technically correct. You may be thinking of big theta notation, which requires both an upper bound and lower bound.

This example is helpful: https://en.wikipedia.org/wiki/Big_O_notation#Use_in_computer...

nayuki2• 10 years ago

You are right. I made a mistake, not thinking through big O vs. theta notation. Thanks.

btilly• 10 years ago

Common mistake. When people say O(2^n) they USUALLY mean something closer to 2^O(n).

The reason is that f(n) = O(g(n)) means that for some constant k and integer N, if N < n then |f(n)| < kg(n). In other words "grows no faster than a constant times". However when you've got exponential growth the slightest of things can cause the exponent to be slightly different, or there to be a small polynomial factor.

That was the case in his example. (The exponent was different.)

njharman• 10 years ago

I like this page http://bigocheatsheet.com/

Espcially the graph which hammers home how quickly things go wrong.

rawnlq• 10 years ago

That table is so wrong it makes me mad.

teraflop• 10 years ago

In what way? Having skimmed it, I see a couple of minor mistakes but the bulk of it seems correct.

The chart says you can search a Cartesian tree in O(log n) expected time, but I don't see how that's possible given that there's no ordering between a node's children.

Also, it's possible to do mergesort in O(1) space; in fact, it's one of the exercises in TAOCP, if I recall correctly. But the algorithm is so complicated that nobody uses it in practice.

gameguy43• 10 years ago

Super interesting comparing this to the one we have on Interview Cake: https://www.interviewcake.com/article/big-o-notation-time-an...

I like how Rob Bell's piece has headings with the most common time costs--sorta makes it easier to see at a glance what you're going to get, and I imagine gives folks a quick sense of, "Right, I've seen that! Been /wondering/ what that means."

nathan_long• 10 years ago

Nice! Very succinct and clear. I wrote an intro myself, as someone who'd recently learned the concept. Wordier, but might be helpful if you think like I do. http://nathanmlong.com/2015/03/understanding-big-o-notation/

emodendroket2• 10 years ago

It would be sensible to put the terms like "constant" and "logarithmic" in there, IMO.

curiousDog2• 10 years ago

I think the nicest way to learn this if you don't have a formal CS education is to still pick up a Discrete Math text book (like Chapter 3 in Rosen) and then read chapters 3 and 4 in CLRS.

stcredzero• 10 years ago

If something puzzles you, don't be afraid to start drawing yourself a diagram. O(n^2) vs. O(n) amortized for naive string concatenation vs. growing a buffer by doubling:

  x
  xx
  xxx
  xxxx
  xxxxx
  xxxxxx
  xxxxxxx
  xxxxxxxx

  x
  xx
  xxxx
  xxxxxxxx

This can be a good way of getting an intuitive feel for what's going on. Note in the 2nd case, you can stack all of 1st two rows representing cost into the 3rd row. In fact, you can always stack the execution costs into row (n-1) and never exceed the size of row n.

curiousDog2• 10 years ago

Looks like you're alluding to the recurrence tree method for solving recurrences mentioned in CLRS. And you're right, it's a great way to visualize and get an intuitive feel of big-oh

krat0sprakhar2• 10 years ago

On the topic of efficient algorithms, I recently read a nice note in an Algorithms textbook -

It would appear that Moore’s law provides a disincentive for developing polynomial algorithms. After all, if an algorithm is exponential, why not wait it out until Moore’s law makes it feasible? But in reality the exact opposite happens: Moore’s law is a huge incentive for developing efficient algorithms, because such algorithms are needed in order to take advantage of the exponential increase in computer speed.

Here is why. If, for example, an O(2n) algorithm for Boolean satisfiability (SAT) were given an hour to run, it would have solved instances with 25 variables back in 1975, 31 variables on the faster computers available in 1985, 38 variables in 1995, and about 45 variables with today’s machines. Quite a bit of progress—except that each extra variable requires a year and a half’s wait, while the appetite of applications (many of which are, ironically, related to computer design) grows much faster. In contrast, the size of the instances solved by an O(n) or O(n log n) algorithm would be multiplied by a factor of about 100 each decade. In the case of an O(n2) algorithm, the instance size solvable in a fixed time would be multiplied by about 10 each decade. Even an O(n6) algorithm, polynomial yet unappetizing, would more than double the size of the instances solved each decade. When it comes to the growth of the size of problems we can attack with an algorithm, we have a reversal: exponential algorithms make polynomially slow progress, while polynomial algorithms advance exponentially fast! For Moore’s law to be reflected in the world we need efficient algorithms.

fenomas• 10 years ago

In the quote, O(2n) and O(n6) are meant to be O(2^n) and O(n^6), right?

krat0sprakhar2• 10 years ago

Yup, that's correct. Sadly, I can't update the comment now :(

kevindeasis• 10 years ago

Is there a beginner's guide to proving different time complexities?

A beginner's guide to Big O notation (2009)

Related Stories