In the class, you learned the backward substitution to get the time complexity o
ID: 3810052 • Letter: I
Question
In the class, you learned the backward substitution to get the time complexity of a recursive algorithm. For example, the following is what you learned in the class.
M(n) = M(n-1) + 1 // Recurrence relation
M(0) = 0 // Initial condition
M(n) = M(n-1) + 1 // Replace M(n-1) with “M(n-2) + 1”
= [M(n-2) + 1] + 1
= M(n-2) + 2 // Replace M(n-2) with “M(n-3) + 1”
= [M(n-3) + 1)] + 2
= M(n-3) + 3
…
= M(n-i) + i
…
= M(n-n) + n
= M(0) + n
= 0 + n
= n Î q(n)
For the homework, solve the following recurrence relation as described above. You have to present intermediate steps and time complexity as described above.
M(n) = 2*M(n – 1) // recurrence relation
M(1) = 3 // initial condition
Explanation / Answer
M(n) = 2*M(n – 1) // recurrence relation
M(1) = 3 // initial condition
M(n) = 2(2M(n-2) + 1) // Replace M(n-1) with “M(n-2) + 1”
= 4M(n-2) + 2
= 4(2M(n-3) + 1) + 2 // Replace M(n-2) with “M(n-3) + 1”
= 8M(n-3) + 6
…
= M(2n-1) + 1
…
= 2n-1
= q(2n-1)