CODEWITHSUNDEEP
time-complexity
hawarden_
hawarden_

Reputation: 2170

Time complexity : how do we find O(n^3)?

I know f(n) = 3*n^3 + 4*n + 2 has O(n^3) complexity, but I want to know how to calculate it using the definition of big O :

If f(n) has complexity O(g(n)), that means there exists a constant c > 0, n0 >=1 where f(n) < c*g(n)

But how do you determine what is the c and what is the g(n) ?

Upvotes: 0

Views: 55

Answers (1)

Patrick87
Patrick87

Reputation: 28312

You can use any dirty hack you want to divine a c and n0 that work, then prove them (induction usually works well but sometimes is not necessary).

Here, simply note that for n >= 1, n^3 >= n >= 1, so

f(n) = 3*n^3 + 4*n + 2
    <= 3*n^3 + 4*n^3 + 2*n^3
     = 9n^3

This has told us the choice n0 = 1 and c = 9 works. Here we knew the bound and wanted to find constants to verify; if we hadn't known the bound we could have guessed one based on the formula or written out some terms.

Upvotes: 1

Related Questions