University:
Massachusetts Institute of Technology
Course:
16.01 | Unified Engineering I, II, III, & IV
Academic year:

2022
Views:

316

Pages:

1
Author:

Emilee Weeks

C13 1. Solve the following recurrence equation using the iteration method. Show all the steps in your derivation. c n =1  T (n) = aT n + √ cn n > 1 b↵ Substitute the value of T(n) from the recurrence equation: aT(n/b) + cn ⇒ a(aT((n/b)/b) + c(n/b)) + cn ⇒ a2T(n/b2) + cn(a/b) + cn ⇒ a2T(n/b2) + cn((a/b) + 1) ⇒ a2(aT((n/b2)/b) + cn/b2) + cn((a/b) + 1) ⇒ a3T(n/b3) + cn(a2/b2) + cn((a/b) + 1) ⇒ … ⇒ a3T(n/b3) + cn((a2/b2)+ (a/b )+ 1) akT(n/bk) + cn((ak-1/bk-1)+ (ak-2/bk-2)+ … + (a2/b2)+ (a/b) + 1) When k = logb n, ⇒ n = bk T(n) = akT(1) + cn(ak-1/bk-1 + ... + a2/b2 + a/b + 1) = akc + cn(ak-1/bk-1 + ... + a2/b2 + a/b + 1) = cak + cn(ak-1/bk-1 + ... + a2/b2 + a/b + 1) = cnak/bk + cn(ak-1/bk-1 + ... + a2/b2 + a/b + 1) = cn(ak/bk + ... + a2/b2 + a/b + 1)

Solution to C13 Question

of 1

Description

Free up your schedule!

Take 5 seconds to unlock