4 ms·

O(N) is read "Order of N" because the O function is also known as the Order function. I think this is because we're doing approximation, which deals in "orders

O(N) is read "Order of N" because the O function is also known as the Order function. I think this is because we're doing approximation, which deals in "orders of magnitude". It's a different meaning of "order", that has to do with the shape of the size-vs-time curve. It's the same meaning as the order of a polynomial ("x" is linear or 1st order, "x^2" is quadratic or 2nd order, etc). but Big-O is all about the approximate worst-case performance of doing something. It can be, but I think it's more commonly taken to mean the average case. One example is quicksort, which is O(n*log(n)) on average but can be quadratic (n^2) in the worst case.

justinlilly 13y ago
Thanks for your comment. I must admit that my lack of mathematical background makes your clarification difficult to understand. I've not heard the term "order of a polynomial". If you wrote up a post and emailed me at justin@abrah.ms explaining the concept, I'd happily link it in this article. :)
- Ixiaus 13y ago
  I'm self taught too. Pick up Knuths books and start going through them, stop and learn the math if you don't understand it. His first book in particular begins with some mathematical foundations that will dramatically change how you reason about your programs. This stuff isn't scary. It's thick but learnable and you can even develop an appreciation for its elegance.
Dewie 13y ago
And when talking about the running time of an algorithm with O-notation, concerns about whether or not an algorithm is faster by a constant factor (for example three times faster, an order of magnitude faster, two orders of magnitude faster) compared to another algorithm is not captured by the O-notation by convention (it is abstracted out, so to speak). If you find out that an algorithm is O(2n), you simplify it to O(n) (the coefficient of n does not matter).
jfarmer 13y ago
More importantly, although "O" is a function, one doesn't usually think about it that way. If one were, I think it's important to be precise. Here's the best crack I can take at it, though. Let ℜ be the set of all real numbers. Let F(ℜ) be the set of all functions f: ℜ → ℜ. Let X be a set and 𝒫(X) be the power set of X, i.e., the set of all subsets of X. Then "O" is a function O: F(ℜ) → 𝒫(F(ℜ)) such that O(g) = { f ∈ F(ℜ) : limsup_{x→∞} f(x)/g(x) < ∞ } That is, O takes as its input a function from the reals to the reals and returns a set of all functions which are in its "Big-O" class. That seems really, really pedantic and not particularly illuminating.

justinlilly 13y ago

Thanks for your comment. I must admit that my lack of mathematical background makes your clarification difficult to understand. I've not heard the term "order of a polynomial". If you wrote up a post and emailed me at justin@abrah.ms explaining the concept, I'd happily link it in this article. :)

Ixiaus 13y ago
I'm self taught too. Pick up Knuths books and start going through them, stop and learn the math if you don't understand it. His first book in particular begins with some mathematical foundations that will dramatically change how you reason about your programs. This stuff isn't scary. It's thick but learnable and you can even develop an appreciation for its elegance.

Dewie 13y ago

And when talking about the running time of an algorithm with O-notation, concerns about whether or not an algorithm is faster by a constant factor (for example three times faster, an order of magnitude faster, two orders of magnitude faster) compared to another algorithm is not captured by the O-notation by convention (it is abstracted out, so to speak). If you find out that an algorithm is O(2n), you simplify it to O(n) (the coefficient of n does not matter).

jfarmer 13y ago

More importantly, although "O" is a function, one doesn't usually think about it that way. If one were, I think it's important to be precise. Here's the best crack I can take at it, though. Let ℜ be the set of all real numbers. Let F(ℜ) be the set of all functions f: ℜ → ℜ. Let X be a set and 𝒫(X) be the power set of X, i.e., the set of all subsets of X. Then "O" is a function O: F(ℜ) → 𝒫(F(ℜ)) such that O(g) = { f ∈ F(ℜ) : limsup_{x→∞} f(x)/g(x) < ∞ } That is, O takes as its input a function from the reals to the reals and returns a set of all functions which are in its "Big-O" class. That seems really, really pedantic and not particularly illuminating.