Give the time complexity for the following algorithm using two different approac

Question

Give the time complexity for the following algorithm using two different approaches. You need to identify the basic operation first.

F(int n) {

if(n > 1)

return 2 * F(n-1);

else

return 1;

}

1) What is the basic operation?

2) Set up the recurrence. Let T(n) be the # of basic operations

3) Use backward substitution to solve the recurrence and indicate the time complexity.

4) Write an iterative algorithm to solve the same problem.

5) Consider the iterative algorithm and the recursive algorithm for this problem, which one is better? Justify your answer

Explanation / Answer

1) basic operation is when n<1, then base case works

2) T(n)=2*T(n-1)+1

3) takes linear time O(n)

4) if (i<1)

f=1;

else

for(i=2;i<n;i++)

f=2*i;

5) In most of the cases recursive works well, but this is one of the exceptional case where both algs works good, as only for lopp and also which runs according to n, i.e. linear time O(n).

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.