I Dont know how to prove them mathematically I know the cons

I Don\'t know how to prove them mathematically, I know the consepts of ignoring the lower terms

Prove that the function f (n) = 2n^3 + 2n^7/3 + log_2n + 5 is O(n^3(). Prove that the function f(n) = (log_2 n)^2 is O(n). Prove that the function f(n) = 2^n + 3 is Theta (2^n)

Solution

In order to answer these question, we must know the definition og big-oh.

For a function, f(n) = O(g(n))

c*g(n) >= f(n) for some value of c and n>n0.

a.) f(n) = 2n^3 + 2n ^(7/3) + log n + 5

c*n^3 >=f(n); for some value of C it must be greater than that of f(n)

therefore, f(n) = O(n^3)

b.) f(n) = (log n )^2

now, c*n >= (log n)^2; for some value of c, c*n will always be greater than f(n)

therefore, f(n) = O(n)

c.) For a function f(n) = theta (g(n)), it must follow given condition:

c1*g(n) <= f(n) <=c2*g(n); for value of c1, and c2.

c1*2^n <=2^(n+3) <= c2* 2^n; where c must be less than 8 and greater than 8.

therefore, f(n) = theta (2^n).

Hope it helps, do give your response.