Difficult Reccurance

Question

Solve the recurrences.

A)  T(1) = 1, T(2) = 6, T(3) = 13, and for all n ≥ 4, T(n) = T(n − 3) + 5n − 9.

B)  T(1) = 1, and for all n ≥ 2, T(n)=2T(n − 1) + n2 − 2n + 1.

Answer 1

Asymptotic Answers ..
a. T(n) = T(n − 3) + 5n − 9
    T(n) = T(n − 3) + O(n)
    Level Cost = O(n), Number of Level = n/3 = O(n)
    T(n) =  Number of Level *  Level Cost = O(n) * O(n) = O(n²)

b.  T(n)=2T(n − 1) + n² - 2n + 1  
     T(n)=2T(n − 1) + O(n²)
     each time two function call, Number of Level = n
     T(n) = O(2ⁿ)

Comments

level cost and Number of levels here means ?

---

II^nd  is T(n)=2T(n − 1) + O(n2)    

which gives T(n) = O(2ⁿ * n²)

Answer 2

T(n) =T(n-3)+5n- 9

T(n)=T(n-3)+O(n)

Now use T(n)=aT(n-b)+O(n^k)

Condition if a=1 then T(n)=O(n^(k+1))

So and is O(n^2)

2- for second use conditiontion

If a>1 then T(n)=O{n^k a^(n/b)}