Practical Session #3 - Recursions Guess the form Substitution of the solution method and prove it by induction Convert the Iteration recurrence into a Method summation and solve it a recurrence of the form: T(n) = aT(n/b) + f(n) a 1 , b ≥ > 1 if f(n) = > 0 ε then = ) if f(n) = Master Method then = log n) if f(n) = > 0 ε and af(n/b) ≤ cf(n) for c < 1 then = Θ(f(n)) Question 1
Practical Session #3 - Recursions Substitution method Guess the form of the solution and prove it by induction Iteration Method Convert the recurrence into a summation and solve it Master Method a recurrence of the form: T(n) = aT(n/b) + f(n) a ≥ 1 , b > 1 if f(n) = ε > 0 then = if f(n) = then = n) if f(n) = ε > 0 and af(n/b) ≤ cf(n) for c < 1 then = Θ(f(n)) Question 1 log )