Demonstrate that fn 5 32log3n 23log2n is Theta n3 Remembe

Demonstrate that f(n) = 5 + 3^2log)_3n + 2^3log2^n 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.

Solution

Answer:

We have given, f(n) = 5 + 3^2logn + 2^3logn

   = 5 + 3^logn^3 + 2^logn^3

   = 5 + n^2 + n^3 [ klogn = logn^k ]

therefore f(n) = n^3 + n^2 + 5

g(n) = n^3

To prove that f(n) = theta(g(n) , we have to prove that :

1. f(n) = O(g(n))

2. f(n) = omega(g(n))

For Big- O notation , we have :

f(n) < = c1 * g(n)

n^3 + n^2 + 5 < = c1 * n^3

let c1 = 10 , n = 1

1 + 1 + 5 < = 10 * 1^3

7 < = 10

therefore f(n) = O(g(n))

2. For Omega notation , wec have

f(n) > = g(n)

n^3 + n^2 + 5 > = n^3

let c1 = 1 , n = 1

1 + 1 + 5 > = 1 *1

therefore f(n) = omega (g(n))

Thus we can say that f(n) = theta(g(n) = > n^3 + n^2 + 5 = theta(n^3)