Find which recurrence relaton is not polynomial?

Question

If T (0) = T (1 ) = 1, each of the following recurrences for n ≥ 2 defines a function T on the non negative integers. Which of the following CANNOT be bounded by a polynomial function?

• A. T ( n)  = 3T(n/2)+  n²
• B. T(n)=  T(7n/8)+ 8n
• C. T (n)= 2T(n-2)+1
• D. T (n)= T(n-1)+ n²

How to solve this?

Please explain

Answer 1

When we are solving option (c) $T(n)=2T(n-1)+1$ the solution will be $T(n)=2^{n+1}-1$, which is exponential order. (This is the recurrence corresponding to Tower of Hanoi).

and by applying masters theorem to others we will get Option (A) is $n^2$, option(B) is $n$ and option(D) is $n^3$

Answer is C

Comments

in option c its  T (n)= 2T(n-2)+1 not T (n)= 2T(n-1)+1 which u are giving of tower of hanoi.anyway answer will be sameT(n)=2T(n−1)+1T(n)=2T(n−1)+1

---

Ok. Sorry for the mistake

Answer 2

W Can This Question as-