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 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
Find and solve a recurrence relation for the number of ways to stack n poker
chips using red, white and blue chips such that no two red chips are together.
Use your solution to compute the number of ways to stack 15 poker chips.
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
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