# Solve the Recurrence and Find the Asymptotic Bound

1. Solve the recurrence exactly and prove your solution is correct by induction.

T(1) = 1 , T(n) = 2T(n-1)+2n-1

T(1) = 1, T(n) = T(n-1)+3n-3

2. Give asymptotic bound for the following:

T(n) = 9T(n/3)+n2

T(n) = T(Sqrt(n))+1.

https://brainmass.com/math/algebra/recurrence-asymptotic-bound-43761

#### Solution Summary

A recurrence is solved and an asymptotic bound is found. The solution is detailed and well presented.

$2.19