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;} [2%] What is the basic operation? [2%]Set up the recurrence. Let T(n) be the # of basic operations. T(n) = [4%] Use backward substitution to solve the recurrence and indicate the time complexity. [4%] Write an iterative algorithm to solve the same problem. [2%] Consider the iterative algorithm and the recursive algorithm for this problem, which one is better? Justify your answer.

Explanation / Answer

F(int n)
{
if(n > 1)
return 2*F(n-1);
else
return 1;
}
1. The basic operation here is the multiplication, in the expression 2*F(n-1).
2. The recurrence is:
T(n) = T(n-1) + 1.
T(1) = 0.
3. Using backward substitution to solve the recurrence:
T(n)
= T(n-1) + 1
= T(n-2) + 2
= T(n-3) + 3
=
=
= T(n-(n - 1)) + n = T(1) + n = n. This belongs to O(n).
4. Iterative algorithm to solve the algorithm:
F(int n)
{
int product = 1;
for(i = n; i > 1; i--)
product *= 2;
return product;
}

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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