Question

1) For the following functions, find the basic efficiency class it belongs to (as Theta of). Must prove your assertion. You may use any theorems stated in Chap2.pdf. (n 2+1) 10 2) Solve the following recurrence and identify the efficiency class they belong to (as Theta of): T(n) = T(n/3)+1 for n > 1 and T(1) = 1. Assume n is a power of 3

Answer 1

To determine the efficiency class of a function, we need to find its Theta notation. For (n^2+1)10^2, it belongs to the Theta(n^2) class. For T(n) = T(n/3) + 1, its efficiency class is Theta(log n).

Step-by-step explanation:

In order to determine the efficiency class of a function, we need to find its Theta notation. Theta notation provides an upper and lower bound on the growth of a function.

For the function (n^2+1)10^2, we can simplify it to n^2. Since the function grows proportionally to n^2, we can say that it belongs to the Theta(n^2) efficiency class.

For the recurrence relation T(n) = T(n/3) + 1, we can see that it divides the problem size by 3 in each recursive step. Since the problem size reduces by a constant factor of 3, we can determine its efficiency class as Theta(log n).