A Beginners’ Guide to Big O Notation

Pretty flawed, unfortunately. I left this as a comment, but it has yet to be moderated through.

----

You’re doing a good thing by trying to elucidate basic concepts, but I’m afraid your article has a bunch of errors that means it’s not as helpful as it could be.

“Big O specifically describes the worst-case scenario” - this isn’t true. g(n) = O(f(n)) simply means that f(n) asymptotically bounds g(n) as n->inf - but the functions involved could be anything and don’t necessarily refer to the worst case. For example, they could be the average case running times of an algorithm, or something completely different. Also remember that for any n, g(n) could be > f(n), so f(n) is not worst case in that respect either.

“O(1) describes an algorithm that will always execute in the same time (or space) regardless of the size of the input data set.” - curiously, also not true. It just means that there’s eventually an upper limit on how much space an algorithm will use, or that eventually as n gets larger the resource consumption of the algorithm becomes constant.

“The example below also demonstrates how Big O favours the worst-case performance scenario; a matching string could be found during any iteration of the for loop and the function would return early” - same point about g(n) = O(f(n)) not being worst case necessarily - you’ve set the problem up so that N is the worst (and average) case running time. However we can say that the best case running time of linear search is O(1).

“O(2^N) denotes an algorithm whose growth will double with each additional element in the input data set.” - also you need to remember that these are upper bounds, and aren’t necessarily tight. That linear search example, which you wrote as O(N), is also O(2^N). If we replace O by \Theta then we begin to get to the behaviour you’re describing, but remember that these things only are true as N gets sufficiently large.

Don't listen to what this article has to say - it's not worth it.

Read the chapter on growth of functions in CLRS instead (a preview at http://books.google.com/books?id=NLngYyWFl_YC&lpg=PP1... - gives the general idea, although it's missing a couple of pages).

Leaving aside actual errors pointed out in other comments, is this article even understandable to a beginner? Having learned and absorbed this stuff years ago, it's hard for me to be sure, but my impression was that it assumed the reader knew lots of things few beginners would.

One example: "O(1) describes an algorithm that will always execute in the same time (or space) regardless of the size of the input data set." What does always executing in the same time (or space) really mean? I know, but I doubt a beginner would.

(As an aside, the use of "complexity" here is unfortunate. It's a wretched term for what it describes. Computer science is full of lousy terminology, but "complexity" is surely among the worst.)

Aside from undefined vocabulary, the common O values are introduced out of order. O(n) is by far the easiest to understand; it should therefore go first, with both a contrived example and a real one. The rest of the document should follow on from there, comparing to O(n).

Good quick read and refresher. I look forward to future articles in this style. :)