Search code examples
big-otime-complexityasymptotic-complexity

Big O notation of simple expressiosn

Why

2n^2 = O(n^3)

As definition says 

if f(n)<= cg(n), 
 n ,c > 0 
for all n > n0

and since there can be many upper bounds So any other and better Upper bound

Solution

  • Definition from Skiena:

    f(n)=O(g(n)) means c·g(n) is an upper bound on f(n). Thus there exists some constant c such that always f(n) ≤ c·g(n), for large enough n (i.e. , n ≥ n0 for some constant n0).

    Here f(n) = 2n^2, g(n) = n^3 Let's take constant c = 2. So 2n^2 <= 2n^3 for n >= 1. So it is true.

    Of course you can show the same way that it is O(n^2) for same c = 2

    From wiki:

    A description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function.