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.

Answer 2

A) T(n) = 3T(⌊n/2⌋) + n² (Master Method)

a = 3, b = 2, f(n) = n²

n^(log_b a) = n^(log₂ 3) ≈ n^1.585

Since f(n) = n² = Ω(n^(log₂ 3 + ε))
and regularity condition holds,

T(n) = Θ(n²)

Polynomially bounded.

B) T(n) = T(n − 1) + n² (Expansion)

T(n) = T(n−1) + n²
     = T(n−2) + (n−1)² + n²
     ...
     = T(0) + Σ i²  (i = 1 to n)

Σ i² = Θ(n³)

T(n) = Θ(n³)

Polynomially bounded.

C) T(n) = T(⌊7n/8⌋) + 8n + 1 (Recursion Tree)

Level 0 cost: 8n
Level 1 cost: 8(7/8)n
Level 2 cost: 8(7/8)²n
...
Level k cost: 8(7/8)^k n

Height: (7/8)^k n = 1 ⇒ k = Θ(log n)

Total cost:
8n [1 + (7/8) + (7/8)² + ...] = Θ(n)

Polynomially bounded.

D) T(n) = 2T(n − 2) + 1 (Expansion)

T(n) = 2T(n−2) + 1
     = 2²T(n−4) + (2 + 1)
     ...
     = 2^k T(n−2k) + (2^k − 1)

n − 2k = 0 ⇒ k = n/2

T(n) = Θ(2^(n/2))

Exponential growth.
Not polynomially bounded.

Final Answer

Correct Option: D