4. Solve the following recurrence relations: a) T(n) cn3 2T(n/2) b) T(n) = cr? + 4T(n/2) Show transcribed image text 4. Solve the following recurrence relations: a) T(n) cn3 2T(n/2) b) T(n) = cr? + 4T(n/2)
Answer
a)
k = 3
a = 2
b = 2
bk = 2^3 = 8
a < bk
2 < 8
T(n) = O(n3)
b)
k = 2
a = 4
b = 2
bk = 2^2 = 4
a = bk
4 = 4
T(n) = O(n2 log n)