CODEWITHSUNDEEP
algorithmtime-complexitybig-onotation
user13880264
user13880264

Reputation:

O(n^2) calculation assistance needed

I just can't seem to figure this one out: 5n2 + 3n + 9 = O(n2). Pick c and n0. Prove using f(n) <= c.g(n).

I have tried compressing it into 3n + 9 / c - 5 <= n^2, but I am still unable to find the solution. I think I am just approaching it from the wrong way.

Stackoverflow, please help me! :)

Upvotes: 1

Views: 93

Answers (4)

Eloy P&#233;rez Torres
Eloy P&#233;rez Torres

Reputation: 1177

According to definition:

O(g(n)) = { f(n) : there exist positive constants c and n0 such that 0 ≤ f(n) ≤ g(n) for all n ≥ n0 }

Let's do some math to find a feasible c and n0:

1

If we take n0 = max(1, 3) = 3 then above inequality holds. Also, we know that c ≥ 9 so we can take c = 9 and the job is done as definition requirements are satisfied.

Upvotes: 0

lawruble13
lawruble13

Reputation: 535

Take c=11, and n0=2. Then we want to show f(n) = 5n^2 + 3n + 9 < 11*g(n) = 11n^2 for all n>= n0. Equivalently, show that 6n^2 - 3n - 9 >= 0 for all n >= n0. This expression factors as (6n-9)(n+1) >= 0. This is only negative on (-1, 1.5), so for all n > 2 we have f(n) < c*g(n).

Upvotes: 0

Guilhem Le Moigne
Guilhem Le Moigne

Reputation: 36

I don’t really understand the question but if you only want to prove that "5n^2 + 3n + 9 = O(n^2)", you have to prove that "(5n^2 + 3n + 9)/n^2 -> k in R when n -> +inf". This is rather simple to prove : "(5n^2 + 3n + 9)/n^2 = 5 + 3/n + 9/n^2 -> 5 + 0 + 0"

Upvotes: 0

David Eisenstat
David Eisenstat

Reputation: 65458

You don't have to get the best constants. If you're dealing with polynomials, n0 = 1 can be a good choice because n ≥ n0 implies n2 ≥ n ≥ 1, so

  2              2     2     2      2
5n  + 3n + 9 ≤ 5n  + 3n  + 9n  = 17n ,

and you can set c = 17.

Upvotes: 3

Related Questions