Question

You determined that your algorithm runs in ?(?) = 3?^3 + 2? + 15, therefore you estimated ?(?) = ?(? ). Show how you come to this conclusion and give specific values for ?1 , ?2 , and ?0 .

Answer 1

Θ(g(n)) = {f(n): there exist positive constants c1, c2 and n0 such 
                 that 0 <= c1*g(n) <= f(n) <= c2*g(n) for all n >= n0}

For c1 = 1 and c2 = 20 and N0 = 0, we have

0 <= N³ <= 3?³ + 2? + 15

and, 0 <= 3?³ + 2? + 15 <= 20N³

Hence, from the above two equations, we can say that

T(N) = Θ(N³​​​​​​​)