Big-O notation

1. There are often mathematical proofs for the time taken for algorithms, but usually you can come up with the time by analyzing what's going on.

2. Dunno...I assume they're the same but I'm not sure.

3. It's generally the typical case. Most good descriptions of an algorithm will have all three--typical, best, and worst.

4. Not sure, but I'm reading this so it might come in handy, not sure yet. And learn to use Google.

[edited by - Promit on April 23, 2004 8:02:57 PM]

well yes, i do use google...



right. those slides cleared up quite a few things. thanks.

Big O notation is used to indicate the running time(or memory consumption) of a program as a function of the size of its inputs.

O(n) means that doubling the input size will double the output.
O(log n) means that doubling the input size will add one to the output.
O(n^2) means that doubling the input size will quadruple the output.

1. Only the largest term is important - it dominates the others.

2. O is an upper bound. Omega is a lower bound. Theta is a tight bound - if f(x) is O(g(x)) and Omega(g(x)) then f(x) is theta(g(x))

3. Usually average case, if not it''ll be specified. Quicksort is called O(n logn), even though its worst case is N^2.

4. Asymptotic performance is what we''ve been talking about - how changing the inputs affects changing the outputs. Asymptotes are the lines that you draw around a function, showing that the function reaches that line as it approached infinity. For that reason, remember that because your input will be finite, asymptotic analysis may not tell you the whole story. An O(2^n) algorithm will still run plenty fast for N < 20.

thanks! that explained everything

now i can happily go back to coding flash things with slightly-more-than-no-knowledge of the theory

quote:

---

Original post by Qatal
I''ve noticed this comes up a lot, and because I don''t have a computer-science background, dont really understand.

I''ve figured its about the "complexity" of the algorithm as a function of the number of items or something.

I also know that O(n) is good. O(lg n) is better.
O(n^2) is bad, because it increases exponentially,

---

Quadratically. Sorry, pet peeve of mine. I''ve even heard people say "exponential" to mean "faster than linear" in general. Wrong wrong wrong. >_<

Anyway. To be a bit more rigorous about what was said before... consider f(n) = the time the algorithm takes for input of size n. Let g(n) be some simple candidate function (like n, n^2, n lg n etc... basically anything you might see in the O() brackets).

If there exists constant C, x such that f(n) <= C*g(n) for all n >= x, then f(n) is in O(g(n)). Similarly: if for all C, there is some x such that f(x) > C*g(x), then f(n) is in Omega(g(n)). (I think I got the technicalities right, but not sure.) Note "is in"; the "orders" of functions are technically sets, but we usually just say "is".

If we can find g(n) such that f(n) is in O(g(n)) and also in Omega(g(n)), then f(n) is in Theta(g(n)) (that''s your O with the bar).

Of course, in the Real World, practical limits on n matter, as do the constant factors that get abstracted out, as do weird things that can influence those "constant" factors in strange ways (think cache locality). However, as a general rule it is a good idea to assume that your client''s data sets will some day be much bigger than the ones you are testing with. (The same reason why you use dynamically allocated arrays and STL containers, yeah?)

Is it just me or did anyone else thing that the notion usually meant the worst cast senario?

quote:

---

I also know that O(n) is good. O(lg n) is better.
O(n^2) is bad, because it increases exponentially,
O(n^3) is bloody evil (radiosity, anyone)
and O(n lg n) is considerably better than O(n^2).

---

Uh, no.

I think you''re confusing exponential with convex up, which is not really the issue here. O(n^2) is only bad when it''s worse than it could be. If you could find an algorithm to multiply two matrices in O(n^2) time, you could probably sell it for a million dollars.

O(n^2) is worse than O(n^2), but it''s not really that bad.

Bloody evil are O(n!) and O(e^n). The last one was correct (but it''s worse than O(n), so it can''t be that much better).

Time and space complexity functions are constructed by summing steps and multiplying the steps inside loops by the number of times the loop is executed. Then, O, o, and big-theta are properties of this function. O is the upper bound, o is the lower bound, and big-theta is both. (big-theta(f(n)) => O(f(n)) and o(f(n)))

Average case time and complexity functions are separate functions that are constructed in a somewhat different way, and O, o, and big-theta are also properties of these functions.

It''s also possible to construct best and worst case time and space complexity functions and analyze them the same way, in which case T(n) = O(n) => (worst-case T)(n) = big-theta(n). (similarly for best-case) This isn''t seen very often.

You know what horizontal and vertical asymptotes are? Do you also know what slant asymptotes are? They''re kinda like a horizontal or vertical asymptote in that a function converges on it as x->infinity, but instead of a constant value, it converges on a line. The easiest example is the asymptote of a hyperbola of canonical form x^2 - y^2 = 1. This converges on the line x=y.

Well, big-theta is a lot like this, except that instead of converging on a line, a function "converges" on f(n) (the inside of the big-theta). The definition doesn''t actually require that it converge, it just requires that at some point, it be between two similar curves for all points beyond that point, but it gives you an idea of the concept.

So when time-complexity is O(n), it''s said to have linear (the n part) asymptotic (the O part) performance (the time-complexity part).

Hmm, I always thought matrix multiplication algorithm *was* O(n^2).
The only one I know of that is slightly better is something like O(n log n) but only for exceedingly large sparse matrices.

Maybe you were a jokin'' or it was a typo...

Oops my bad, it was O(n^3) and some better ones that exist that are O( n ^ x) where x > 2 and less then 3 (Strassen''s algorithm)..

I was thinking of some FFT algorithm that I thought reduced it to O(n^2). My brain is real tired :-)

Peace

For those who care: &Theta; == Θ and &Omega; == Ω

The FFT matrix multiplication algorithm runs in O(n^{log₂ 7}), about O(n^2.81). It splits the matrix up into 4 submatrices of equal size (or off by 1 if the matrix is of odd length), and then using a series of clever additions and subtractions, it takes only 7 multiplications (instead of the normal 8) to get the product. Thus, the recursive relationship is recursively f(n) = 7 f(n / 2), and the solution to that is f(n) = O(n^{log₂ 7}).