Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Big-O notation explained by a self-taught programmer

justin.abrah.ms

Post reply on HN
Print view View original

61–70 of 80 posts

Re: Big-O notation explained by a self-taught programmer

#61

Post by jfarmer »

tbrownaw wrote: post #9

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 appro…

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.

Re: Big-O notation explained by a self-taught programmer

#62

Post by oskarkv »

First of all, O(g(n)) is a set. It is the set of functions f(n) such that there exists positive constants n0 and C, and C*g(n) > f(n) when n > n0.

Second, talking about O(g(n)) does not imply that the time complexity being discussed is the worst-case (or any other case) time complexity. One could for example say that the algorithm A's best-case time complexity is in O(n), and it's worst-case time complexity is in O(n^2).

Re: Big-O notation explained by a self-taught programmer

#63

Post by algorias »

nhamann wrote: post #43

This article has way too many words and not enough math. There is, in fact, nothing scary about big O notation once you dissect it, and it's a shame that so many people seem to think otherwise. Here's the definition: if f and g are functions (let's say real-valued functions defined on the positive reals), then we say that f is big O of g , written f = O(g), if there exists a real number y and a real number K, K > 0,…

> Also could be because in practice algorithms with wildly varying constant factors out in front are rarely seen?

The main reason is that you want a result that does not depend on small implementation details, i.e. is consistent across programing languages and CPU architectures.

Things as simple as larger cache size or a slightly better hashing function in a dict can increase the running speed of a program by a constant factor.

Re: Big-O notation explained by a self-taught programmer

#64

Post by jfarmer »

foobarbazqux wrote: post #30
baddox wrote: post #27

Earlier quoted context omitted.

Of course. But it's also the worst case. I'm really just wondering if there's a "default" scenario that's being referred to when we just say "f(n) is in O(n)" or does it depend on context?

Quicksort is the exception, in my experience big-O usually refers to worst case running time as opposed to average case or expected running time. CLR(S) [1] sticks to worst case because 1) worst case is a guarantee; 2) the worst case can be frequent; 3) the average case is often roughly as bad as the worst case. This is a widely used textbook, so I generally assume a lot people follow its conventions. [1] https://mit…

It's also not obvious what "average case" means. For example, if we're talking about the asymptotic behavior of the function

  A(n) = avg { RunningTime(Algo, x) : x is valid input to Algo and len(x) = n }
are we assuming that the inputs are drawn uniformly and therefore have equal weight or are we drawing them from a non-uniform distribution? What if some inputs never occur in practice?

Worst case and best case are totally unambiguous and don't need any additional clarification. There are just so many knobs one can adjust when defining "average".

Re: Big-O notation explained by a self-taught programmer

#65

Post by Retric »

ericholscher wrote: post #37
YZF wrote: post #32

The math of Big-O isn't that hard and the article while having good intentions misses the point. Big-O is about asymptotic behaviour and the graphs are misleading in that regard (well, they're simply wrong, not misleading). There are algorithms where if you just look at the Big-O you'd think one has faster run time than the other but because the constants fall out that wouldn't be the case for any practical problem s…

As a data point, I have no idea what you just said.

Suppose you had three functions.

  F1(n) = 1 second * n + 1 day = O(n)
  F2(n) = 1 millisecond * n + 1 month = O(n)
  F3(n) = 1 nanosecond * n ^ 2 + 1 millisecond = O(n^2)
For really big numbers both F1 and F2 are faster but at n = 100 F3 has a huge lead and for say n = 1 billion F3 beats F1 but not F2.

Re: Big-O notation explained by a self-taught programmer

#66

Post by tsahyt »

kyllo wrote: post #39
ericholscher wrote: post #37

Earlier quoted context omitted.

As a data point, I have no idea what you just said.

He's saying that big O only matters for big input sizes, because big O is specifically about the algorithm's asymptotic performance, which means its performance for a large value of n. If you have a small value of n then the other constant time operations in the algorithm may affect the running time more. n^2 is less than n^3 right? But is 2 * n^2 + 100 less than n^3? Depends on how big n is, right? Big O notation ju…

More or less, yes. What he is saying is that there is a constant hidden in the big O. Say, we have two algorithms A and B with a runtime that can be bounded by the functions a(n) = 1000n^2 and b(n) = 0.001n^3 respectively. Hence a ∈ O(n^2) and b ∈ O(n^3). So the first algorithm A is clearly faster asymptotically. However, suppose we have input sizes of around n=50000, it actually turns out that algorithm B is faster because g(50000) 10000000 in this case), algorithm A will always be faster.

A good implementation could check problem sizes beforehand and chose the algorithm accordingly.

What I don't agree with is that "big O only matters for big input sizes". Big is not really a well-defined term. The problem here is that "big" depends entirely on the algorithms. It might also be n > 10. There's nothing in the definition of the landau symbols that prevents that.

Re: Big-O notation explained by a self-taught programmer

#67

Post by fmax30 »

oskarkv wrote: post #60
fmax30 wrote: post #58

I don't really know why Big-O notation is so common , even though Big O is the upper bound . For me it is more practical and logical to use the Big Θ (Theta) notation as it provides a tighter bounder which is more understand able. Also Big O is very misleading to the new comers, as they are usually confused when they see something like O(n) = O(n^2) which is perfectly valid , as the Big O notation is only the upper b…

Of course O(n) is not equal to O(n^2). O(n) is a set, and O(n^2) is a different set.

Big O is a upper bound , what I meant was that if a piece of code has O(n) then it also has O(n^2). With emphasis on the upper bound f(x) = O(g(x)) if f(x) g(x).

so my point is if f(N) = O(N) then f(N) is also equal to O(N^2) as f(N) N^2 .

Re: Big-O notation explained by a self-taught programmer

#68

Post by fizz_and_buzz »

yid wrote: post #10

Unfortunately, there are some misconceptions that are propagated in this article. Kudos on the effort, but some statements are just flat out wrong, such as this statement: "Big-O is all about the approximate worst-case performance". Big-O has nothing to do with worst-case, but is a bounding function. An O(n) algorithm is also O(n^2), O(2^n), etc. Those are valid bounds on the O(n) algorithm, just not the smallest.

> An O(n) algorithm is also O(n^2), O(2^n), etc.

To be fair, it is pretty common to be a little bit sloppy with this definition. People often say O(...) when they really mean Θ(...).

Re: Big-O notation explained by a self-taught programmer

#69

Post by gnuvince »

YZF wrote: post #32

The math of Big-O isn't that hard and the article while having good intentions misses the point. Big-O is about asymptotic behaviour and the graphs are misleading in that regard (well, they're simply wrong, not misleading). There are algorithms where if you just look at the Big-O you'd think one has faster run time than the other but because the constants fall out that wouldn't be the case for any practical problem s…

I think that Sedgewick's tilde notation [1] is nice if you want to include more information about constant factors.

[1] http://algs4.cs.princeton.edu/14analysis/

Re: Big-O notation explained by a self-taught programmer

#70

Post by kazagistar »

yid wrote: post #10

Unfortunately, there are some misconceptions that are propagated in this article. Kudos on the effort, but some statements are just flat out wrong, such as this statement: "Big-O is all about the approximate worst-case performance". Big-O has nothing to do with worst-case, but is a bounding function. An O(n) algorithm is also O(n^2), O(2^n), etc. Those are valid bounds on the O(n) algorithm, just not the smallest.

While the mathematics use a bounding function, I am not sure how vital this is to a self taught programmer who is just trying to get insight into some algorithm.
Post reply on HN