Question

Prove or disprove the following statements, using the relationship among typical growth-rate functions seen in class.

a) n^22*log(n)+n^7 is O(n^7*log(n))

b) 10^7*n^5 + 5*n^4 + 9000000*n^2 + n is Θ(n^3)

c) n^n is Ω(n!)

d) 0.01*n^9 + 800000*n^7 is Θ(n^9)

e) n^8 + 0.0000001*n^5 is Ω(n^13)

f) n! is O(3^n)

Answer 1

A)

from definition of Big O , g(n) <= f(n)

g(n) = is greater than f(n) =

This equality is incorrect

B)

g(n) = , from definition of Big Theta , g(n) = f(n)

f(n) =

f(n) is not equal to g(n)

C)

from definition of Big Omega , g(n) >= f(n)

g(n) = n^n

This inequality holds , g(n) > f(n)

It is correct

D)

from definition of Big Theta , g(n) = f(n)

g(n) =f(n) =

It is correct

E)

from definition of Big Omega , g(n) >= f(n)

g(n) = n^8

This inequality does not hold, g(n) < f(n)

It is not correct

F)

from definition of Big O , g(n) <= f(n)

g(n) =

But here g(n) > f(n)

It is not correct