If $T$$\left ( 0 \right )$ $=$ $T$$\left ( 1 \right )$ $=$ $1$, each of the following recurrences for $n$ $\left ( \geq \right )$$2$ defines a function $T$ on the nonnegative integers. Which of the following CANNOT be bounded by a polynomial function?
where Floor$\left ( x \right )$ means $\rightarrow$ the greatest integer that is less than or equal to $x$.
- T$\left ( n \right )$ = $3T Floor$$\left ( n/2 \right )$ $+$$n$^$2$
- T$\left ( n \right )$ = $T$$\left ( n-1 \right )$$+$ $n$^$2$
- T$\left ( n \right )$= $T Floor$ $\left ( 7n/8 \right )$$+ 8n$ $+ 1$
- T$\left ( n \right )$ = $2T$$\left ( n-2 \right )$ $+ 1$