I was reading an article and came across the following :

Informally, O(g(n)) can be defined as the set of mathematical functions that contains all functions that don’t “grow faster” than g(n). Thus, all functions below are in the set O(n²): f(n) = n² 3n 2, f(n) = n log(n), f(n) = 3n 1 . Can please anyone tell me how f(n) = n² 3n 2 grows faster than g(n)?

CodePudding user response：

Can please anyone tell me how f(n) = n² 3n 2 grows faster than g(n)?

Here is one way to understand it (a bit informal, but I find it more intuitive).

Let L be limit as n goes to infinity of f(n)/g(n)

If L is infinity then f(n) grows faster than g(n) (numerator overwhelms denominator).

If L is 0 then f(n) grows slower than g(n) (denominator overwhelms numerator)

If L is finite number then they have same (comparable) growth rates.

CodePudding user response：

We can define O(g(n)) as the following set:

O(g(n)) = { f(n) ∶ ∃ c > 0 and n0 > 0 | 0 ≤ f(n) ≤ c ⋅ g(n), ∀n ≥ n0 }

This means O(g(n)) is the set of all functions f(n) which grow slower than g(n) for some constant c and for n ≥ n0. In order to find n0 and c we use a justification like the following:

n² 3n 2 ≤ n² 3n² 2n²
n² 3n 2 ≤ 6n² for c = 6 and n ≥ 1

Now if you just use g(n) = n² obviously f(n) = n² 3n 2 will grow faster than g(n); but by choosing the value of c correctly g(n) will grow faster than f(n) for n ≥ n0.