Plain English Explanation of Big O Notation

http://www.cforcoding.com/2009/07/plain-english-explanation-of-big-o.html

by cletus • 17 years ago

37 4 17 years ago

stcredzero• 17 years ago

An important thing to know: amortized analysis. (Most of you will already know this, of course.) This is especially useful for operations that happen often. This is how we know that an array that grows by doubling its storage when needed has O(1) for adding to the end.

Hint:

    O
    XX
    OOOO
    XXXXXXXX
    OOOOOOOOOOOOOOOO
    XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
    ...

You can always arrange all but the biggest array alongside the biggest array, with one space left over. So you can always amortize the cost of an array copy over the number of add operations that preceded it.

    OOOOOOOOOOOOOOOOXXXXXXXXOOOOXXO
    XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

ckuehne• 17 years ago

Oh my, another handwaving article about Big O Notation. Why does everyone and their mother feel the need to explain this thing in "plain English".

"Big O notation seeks to describe the relative complexity of an algorithm [...]" Relative to what? To the moon and the stars? Big O is a notation to describe the growth rate of functions.

Therefore, you can also use it to describe the memory usage of an algorithm. Even if the author of the article thinks otherwise.

And so on and so forth.

Seriously, I understand the wish to explain this thing clear and simple. But what is so hard about a clear and concise description using maths and some plots?

Or, in John McCarthy's words:"He who refuses to do arithmetic is doomed to talk nonsense.".

boryas• 17 years ago

I agree with your sentiment, and I prefer the mathematical definition of Big-O to hand-wavey descriptions, but the plain English descriptions do have a place in presenting the material, in my opinion. Once you understand the idea of what Big-O is and isn't used to measure or explain, the actual definition makes sense as a translation of those ideas into math. It's like an example that goes with a theorem in a math textbook. Yes, all of the information is technically in the theorem, but that doesn't mean the example doesn't help a student understand.

fburnaby• 17 years ago

Did anybody know that big o notation is more general than either of these articles lets on? These two articles are explaining the use of big-O notation in algorithms, which is just one possible use. The article by Knuth gives a better insight: http://micromath.wordpress.com/2008/04/14/donald-knuth-calcu...

An example of alternative uses for big-O is the description of the "order of error" introduced by taking the Taylor-series truncation of a math function. This is useful in evaluating the accuracy of numerical techniques.

Plain English Explanation of Big O Notation

Related Stories