6. Solve the following recurrence relations
t(n) = t(n-1) + 3 for n>1
t(1) = 0
t(n) = t(n-1) + n for n>1
t(1) = 1
t(n) = 3t(n/2) + n for n>1, n is a power
of 2
t(1) = ½
t(n) = 6t(n-1) – 9t(n-2) for n>1
t(0) = 0 t(1) = 1
Solve the following recurrence relations: (find an asymptotic
upper bound O(?) for each one)
a. T(n) = T(2n/3)+T(n/3) + n^2
b. T(n) = √nT(√n) + n
c. T(n) = T(n-1)+T(n/2) + n
The base case is that constant size problems can be solved in
constant time (O(1)). You can use the induction, substitution or
recursion tree method
1. Using domain and range transformations, solve the following
recurrence relations:
a) T(1) = 1, T(n) = 2T(n/2) + 6n - 1
b) T(1) = 1, T(n) = 3T(n/2) + n^2 - n
Characterize each of the following recurrence equations using
the master method (assuming that T(n) = c for n ≤ d, for constants
c > 0 and d ≥ 1). a. T(n) = 2T(n/2) + √n b. T(n) = 8T(n/2) +
n2 c. T(n) = 16T(n/2) + n4 d. T(n) = 7T(n/3)
+ n e. T(n) = 9T(n/3) + n3.1
Solve the recurrence equations by Substitution
a) T(n) = 4T (n/2) + n, T (1) = 1
b) T(n) = 4T (n/2) + n2 , T (1) = 1
c) T(n) = 4T (n/2) + n3 , T (1) = 1