Demonstrate that fn 5 32log3n 23log2n is Thetan3 Remember

Demonstrate that f(n) = 5 + 3^2log3n + 2^3log2n is Theta(n^3). Remember that big-O is an upper bound. big-Ohm is a lower bound, and big-Theta is a tight bound, i.e. upper and lower. To prove that f(n) is Theta(g(n)) you must prove both that f(n) is O(g(n)) and that f(n) is Ohm(g(n)). Make sure you prove this using the formal definition of big-Theta. not just an intuitive explanation. Simplify your function to prove it.

Solution

After simplifying the function we get f(n) = 5 + n^2 + n^3. First let us prove big-O

We have to show f(n) <= k*g(n) for all n>m and a constant k. In this case lets take k = 2 and m = 5. for n>5 we know that 5+n^2 < n^3 So 5 + n^2 + n^3 < 2*n^3. So f(n) = O(n^3)

Now lets prove big omega

We have to show f(n) >= k*g(n) for all n>m and a constant k. In this case lets take k =1 and m = 0. for n>0 we know that 5+n^2 >= 0 So 5 + n^2 + n^3 > n^3. Which can also be written So f(n) = big omega(n^3)

Combining both we get f(n) = big theta (n^3)