Big O notation mathematical proof [closed]

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 9 years ago.

Improve this question

I am trying to understand what exactly Big O notation is. I understand it in the literal and practical sense by going through the answers of similar questions in SO. But what the answers don't explain and i fail to understand is the mathematical basis behind it. The formal definition states that

  A function T(n) is the Big-O notation of f(n), if and only if there exist two constants c, n0 > 0 such that

   T(n) <= c * f(n)  for all n >= n0. 

I understand intuitively to some extent that this equation tries to calculate the upper bound in terms of some function which has higher slope in the sense, something in the higher end to the function f(n). I know my understanding is vague. So can someone please explain the mathmatical basis/representations of Big-O notation.

Answer 1

First let me just say that if g(n) is a function of n, then O(g(n)) is the set of all functions f(n) such that there exist constants c,N>0 such that f(n) <= cg(n) for all n >= N.

If one analyzes an algorithm exactly, then one comes up with a function of the input size n, say f(n), which might be some complicated annoying polynomial expression in n (or a complicated expression involving an exponential).

For example, one might find that an algorithm, given an input size of n, has exactly f(n) = 2n^2 +3n + 1 instructions. But we don't really care about the 3n + 1 part. If n gets very large, the n^2 term of f will dominate the lower-order terms. For instance, for n=100 we already find that 2*100^2 is a lot more significant than 3*100 + 1.

So, to make this idea more rigorous, we'd like to say that "f(n) grows at worst like n^2". In mathematical notation: f(n) is an element of O(n^2). Now as you've stated in your question, to actually prove that f(n) is an element of O(n^2), we need to find constants c and N such that for all n >= N we have f(n) <= cn^2. So if we try c=3, then we get the inequality f(n) <= 3*n^2, and if you play around algebraically then you'll find that for all n >= 5 this holds true. So our c=3 and our N=5. Indeed, f(n) grows at worst like n^2.

Notice however the words "at worst like". It would be wrong to say "f(n) grows like ...", instead we say "f(n) grows at worst like...".

To give you another example, consider our f(n) = 2n^2 + 3n + 1 again. My claim is that f(n) is not an element of O(n). To actually show that this is true, we need to show that for all c,N>0 there exists an n>=N such that f(n) > cn. Well, f(n) > cn is true if and only if 2n^2 + (3-c)n + 1 > 0, which is true for for sufficiently large n>=N (no matter what N is), of which I'll let you work out the details. This shows that f(n) grows at a worse rate than linear.

Yet another example with our f(n) = 2n^2 + 3n + 1: It can be shown that f(n) is an element of O(n^3). Let's do that, shall we? We need to find c,N>0 such that f(n) <= cn^3 for all n>=N. Well, try c=1; then after some algebra you can find that this is true for N=4. This warrants the "f(n) grows at worst like ..." sentiment; if you can show that your function f is in some big-O, then there might a "better big-O" for which it is part of.

As a final exercise, show that O(1) is a proper subset of O(n), which is a proper subset of O(n^2), which is a proper subset of O(n^3), which is a proper subset of O(n^4), ...

Answer 2

g(n) = O(f(n)) means that after a certain n(for n > n0) g(n)/f(n) <= M(a fixed quantity) For example g(n) = n is both O(n) and O(n*log(n)) as for n0 = 2 :

n/n = 1 <= 1 = M

n/(n*log(n)) <= 1/log(2) = M