Question

1 (10 pts) Give a big-θ bound for the solutions of the following recurrence relations. Show work.

(a) T(n) = 8T(n/2) + n^3 + 100n

(b) T(n) = 5T(n/4) + 3n

(c) T(n) = 7T(n/3) + 100n^2

(d) T(n) = 3T(n/3) + 1000√ n

(e) T(n) = T(n − 1) + n^2

Answer 1

a)


b)


c)


d)


e)
T(n)
= T(n-1) + n^2
= T(n-2) + (n-1)^2 + n^2
= T(n-3) + (n-2)^2 + (n-1)^2 + n^2
= T(1) + 2^2 + ... + (n-2)^2 + (n-1)^2 + n^2
= 1 + 2^2 + ... + (n-2)^2 + (n-1)^2 + n^2
formula for sum of squares of first n numbers is n(n+1)(2n+1)/6
ignore constant terms.
so, time complexity is ?(n^3)
Answer: ?(n^3)