What is the value of the following recurrences?

Question

1 :- T(n) = T(n-2) + n2

2 :- T(n) = 4T(n/3) + nlgn

3 :- T(n) = 3T(n/3 - 2) + n/2

Answer 1

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

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

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

if a>1 then T(n)=O(n^ka^n/b)

---

1) a=1 so its Θ(n²) albeit this recurrence relation is quite simple and can be solve easily.

2) apply master theorem ,

n^log_ba =n^log₃4    = ~n^1.x   and we know logn < n^0.x

so in that way its TC = n^log₃4 

3) Its O(n).