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

Let us prove big-O, let us assume n>5 so for n>5 we know 5+n^2 < n^3. Therefore 5+n^2 + n^3 < 2*n^3. Therefore f(n) = big-O(n^3)

Now let us prove big-O, let us assume n>0 so for n>0 we know 5+n^2 >0. Therefore 5+n^2 + n^3 > n^3. Therefore f(n) = big-Omega (n^3)

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