Test by Bikram | Mock GATE | Test 2 | Question: 44

Question

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$.

• A. T$\left ( n \right )$ = $3T Floor$$\left ( n/2 \right )$ $+$$n$^$2$
• B. T$\left ( n \right )$ = $T$$\left ( n-1 \right )$$+$ $n$^$2$
• C. T$\left ( n \right )$= $T Floor$ $\left ( 7n/8 \right )$$+ 8n$ $+ 1$
• D. T$\left ( n \right )$ = $2T$$\left ( n-2 \right )$ $+ 1$

Comments

@ Bikram,

Can you please explain how to solve this question, i don't even know how to approach such questions.

Answer 1

ANS is D)

1.⊝(n^2),3.⊝(n)  by case III of master theorem.

2.⊝(n^3)  by solving recurrence.

4..⊝(2^n)  by solving recurrence.

Comments

How do you solve 3rd recurrance?

---

Apply Case III of master theorem.