Question

Consider the following function :
F 1 = 2, F n = (F n-1 ) 2 , n ≥ 2
i. What is the complexity of the algorithm that computes F n using the recursive
definition given above.
ii. Describe a more efficient algorithm to calculate F n and give its running time.

Answer 1

`Hey,

Note: If you have any queries related to the answer please do comment. I would be very happy to resolve all your queries.

1)

Given F(n)=F(n-1)^2

So,

we can rewrite it as

F(n)=F(n-2)^4

Again

we can rewrite it as

F(n)=F(n-3)^8

So, the general formula is

F(n)=F(n-k)^(2^k)

So, for k=n-1

F(n)=F(1)*(2^(n-1))=2^n

So, The complexity is

F(n)=O(2^n)

ii)

The best algorithm would be to directly use the formula found in the end in previous part

So,

F(n)=2^n

So, algo is

int power(int x, unsigned int y)

{

    int temp;

    if( y == 0)

        return 1;

    temp = power(x, y/2);

    if (y%2 == 0)

        return temp*temp;

    else

        return x*temp*temp;

}

CALL THE FUNCTION AS power(2,n)

So, it will just be O(log(n)) since it uses divide and conquer algo

Kindly revert for any queries

Thanks.