Vfrdtyky

When we say a method has the time complexity of O(n^2) is it meant in the same way as in 10^2 = 100 or does it mean that the method is at max or closest to that notation? I am really confused on how to undertand Big O. I remember something called upper bound, would that mean at max?

Explanation

If a method f is inside O(g), with g being another function, it means that at some point (exist some n_0 such that for all n > n_0) the function f will always output a smaller value than g for that point. However, g is allowed to have an arbitrary constant k. So f(n) <= k * g(n) for all n above some n_0. So f is allowed to first be bigger, if it then starts to be smaller and keeps being smaller.

We say f is asymptotically bounded by g. Asymptotically means that we do not care how f behaves in the beginning. Only what it will do when approaching infinity. So we discard all inputs below n_0.

Illustration

An illustration would be this:

The blue function is k * g with some constant k, the red one is f. We see that f is greater at first, but then, starting at x_0, it will always be smaller than k * g. Thus f in O(g).

Definition

Mathematically, this can be expressed by

which is the usual definition of Big-O. From the explanation above, the definition should be clear. It says that from a certain n_0 on, the function f must be smaller than k * g for all inputs. k is allowed to be some constant.

Both images are taken from Wikipedia.

Examples

Here are a couple of examples to familiarize with the definition:

• 
  n is in O(n) (trivially)


• 
  n is in O(n^2) (trivially)


• 
  5n is in O(n^2) (starting from n_0 = 5)


• 
  25n^2 is in O(n^2) (taking k = 25 or greater)


• 
  2n^2 + 4n + 6 is in O(n^2) (take k = 3, starting from n_0 = 5)

Notes

Actually,O(g) is a set in the mathematical sense. It contains all functions with the above mentioned property (which are asymptotically bounded by g).

So, although some authors write f = O(g), it is actually wrong and should be f in O(g).

There are also other, similar, sets, which only differ in the direction of the bound:

• Big-O: less equals <=
  


• Small-o: less <
  


• Big-Omega: greater equals >=
  


• Small-omega: greater >
  


• Theta: Big-O and Big-Omega at the same time (equals)

If means that the running time is bounded above by N².

More precisely, T(N) < C.N², where C is some constant, and the inequality is true as of a certain N*.

For example, 2N²+4N+6 = O(N²), because 2N²+4N+6 < 3N² for all N>5.