Design recursive algorithms for the following problems Compu

Design recursive algorithms for the following problems: Compute the n-th Fibonacci number F_n. Recall that the n-th Fibonacci number is defined as follows. F_n = {1 if n = 0, 1 F_n - 1 + F_n - 2 if n greaterthanorequalto 2 Compute the n-th power of a number x, x^n, with n non-negative integer. The algorithm should be designed in such a way that it is possible to write a recurrence relation for the total number of multiplications executed by the algorithm for which the Master Theorem applies. Write such a recurrence and apply the Master Theorem to obtain an asymptotic bound for it.

Solution

3. a.

Fibonacci numbers are computed using the following recursive function.
int Fibonacci(int N) //Given the value of n, the nth fibonacci number is returned.
{
if (N == 0 || N == 1) return 1; //If n == 0, or 1, return 1.
else //For all other numbers.
return Fibonacci(N-1) + Fibonacci(N-2); //F(n) = F_n-1 + F_n-2
}

Algorithm Power(int x, int n):
//Input: the base x, and the exponent n.
//Output: the value of x raised to the power of n.
//Given the value of x, and n, the function computes the value of
//x raised to the power of n, using recursion.
if(n == 0)   //If n is 0, return 1. Any number raised to power of 0 is 1.
return 1;
else if(n == 1)   //If n is 1, return the base. Any number raised to power of 1, is the number itself.
return x;
if(n % 2 == 0)   //If n is even, divide the problem into 2 parts, solve it, and combine with another multiplication.
return Power(x, n/2) * Power(x, n/2);
else           //If n is odd, divide the problem into 2 parts, solve it, and combine with another multiplication.
return Power(x, n/2) * Power(x, n/2 + 1);

The recurrence relation for the number of multiplications is:
T(n) = 0, if n == 0, or 1.
   = 2T(n/2) + 1, otherwise.
And as per Master Theorem, a = 2, b = 2, and f(n) = 1, i.e., O(n^1), therefore, d = 1. And a = b^d, since, 2 = 2^1.
Therefore, the efficiency of the algorithm is: O(n log n)