Question

Consider the following function : F 1 = 2, F n = (F n-1 ) 2...

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.

Homework Answers

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.

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Give a recursive algorithm to solve the following recursive function.    f(0) = 0;    f(1)...
Give a recursive algorithm to solve the following recursive function.    f(0) = 0;    f(1) = 1; f(2) = 4; f(n) = 2 f(n-1) - f(n-2) + 2; n > 2 Solve f(n) as a function of n using the methodology used in class for Homogenous Equations. Must solve for the constants as well as the initial conditions are given.
java data structure question - Consider the following recurrence function" f(1)=1; f(2)=2; f(3)=3; f(4)=2; f(5)=2 f(n)...
java data structure question - Consider the following recurrence function" f(1)=1; f(2)=2; f(3)=3; f(4)=2; f(5)=2 f(n) = 2 * f(n -1) + f(n – 5) for n >= 6 Write a program to demonstrate this recurrence relation (recursive method) and demonstrate it for the values n = 6, 7, 10, and 12; Create a second method that solves the same problem using an iterative solution. Modify your test program to show that both the recursive method and the iterative methods...
Dynamic Programming. Consider the Fibonacci series F(0) = 1; F(1)=1; F(n)=F(n-1)+F(n-2) Define the Dynamic Programming algorithm...
Dynamic Programming. Consider the Fibonacci series F(0) = 1; F(1)=1; F(n)=F(n-1)+F(n-2) Define the Dynamic Programming algorithm for calculating F(5) . How does it compare with the recursive algorithm? in java
QUESTION 1 For the following recursive function, find f(5): int f(int n) { if (n ==...
QUESTION 1 For the following recursive function, find f(5): int f(int n) { if (n == 0)    return 0; else    return n * f(n - 1); } A. 120 B. 60 C. 1 D. 0 10 points    QUESTION 2 Which of the following statements could describe the general (recursive) case of a recursive algorithm? In the following recursive function, which line(s) represent the general (recursive) case? void PrintIt(int n ) // line 1 { // line 2...
Given the three numbers, a, n and m, compute a^n mod m. What is the input...
Given the three numbers, a, n and m, compute a^n mod m. What is the input size and why? What is the brute-force solution for this problem and what is its complexity? Give the most efficient algorithm for this problem that you can, analyze its time complexity T(n), express it as a function of the input size and argue whether or not it is a polynomial-time algorithm.
Consider the following recursive algorithm Algorithm S(n) if n==1 return 1 else return S(n-1) + n*n*n...
Consider the following recursive algorithm Algorithm S(n) if n==1 return 1 else return S(n-1) + n*n*n 1)What does this algorithm compute? 2) Set up and solve a recurrence relation for the number of times the algorithm's basic operation is executed. 3) How does this algorithm compare with the non-recusive algorithm for computing thius function in terms of time efficeincy and space effeciency?
   1)T(n) = 27 T (n/3) + n3 2)Calculate the running time for the following code...
   1)T(n) = 27 T (n/3) + n3 2)Calculate the running time for the following code fragment. Algorithm test int counter, i, j; counter := 0; for (i:= 1; i < n; i*=2) { for (j:= 0; j < i; j++) { counter := counter +1 } } 3)Let f(n) = 2lg 8n + 3 be a function.
Question 4.5 Consider the fragment in Algorithm 4.8 shown below. Algorithm 4.8 sum = 0; for...
Question 4.5 Consider the fragment in Algorithm 4.8 shown below. Algorithm 4.8 sum = 0; for (i =1; i <=f(n); i ++) sum += i; Here f(n) is a function call. Give a simple and tight Big-Oh upper bound on the running time of Algorithm 4.8, as a function of n, on the assumption that (a) the running time of f(n) is O(n), and the value of f(n) is n!. (b) the running time of f(n) is O(n), and the...
Question 4: The function f : {0,1,2,...} → R is defined byf(0) = 7, f(n) =...
Question 4: The function f : {0,1,2,...} → R is defined byf(0) = 7, f(n) = 5·f(n−1)+12n2 −30n+15 ifn≥1.• Prove that for every integer n ≥ 0, f(n)=7·5n −3n2. Question 5: Consider the following recursive algorithm, which takes as input an integer n ≥ 1 that is a power of two: Algorithm Mystery(n): if n = 1 then return 1 else x = Mystery(n/2); return n + xendif • Determine the output of algorithm Mystery(n) as a function of n....
1.) the following code fragments give running time analysis (Big Oh). Explain your answer: sum2 =...
1.) the following code fragments give running time analysis (Big Oh). Explain your answer: sum2 = 0; sum5 = 0; for(i=1; i<=n/2; i++) { sum2 = sum + 2; } for(j=1; j<=n*n; j++) { sum5 = sum + 5; } i think it is O(n^2) since big oh finds the order of worst case which is the the second loop being n^2 complexity. but im not sure. 2.) Give an efficient algorithm along with running time analysis to find the...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT