Question

Give complete proof for the growth rates of the following polynomial. Please provide specific values for c and ng and prove algebraically that the functions satisfy the definitions for O and Q 4p311 g(p) = p e(ps) Prove that g

Answer 1

For a given function g(n), we denote Θ(g(n)) is following set of functions.

Θ(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}

Clearly,

0 <= p⁵ <= p⁵ + 4p³ + 11 for p >= 0

Hence, for c = 1 and p0 = 0, we have

g(p) = Ω(p⁵)

And,

0 <= p⁵ + 4p³ + 11 <= p⁵ + 4p⁵ for p >= 2

Hence, for c = 5 and p0 = 2, we have

g(p) = O(p⁵)

Hence, g(p) = Θ(p⁵)