GATE CS 2003 Q35 — Asymptotic Worst Case Time and Space Complexity

We can solve this recurrence relation by substituting small values of $m$ to eliminate options, or by analytical summation.

Method 1: Substitution (Fastest)

Using the recurrence relation $T(n+1) = T(n) + \lfloor \sqrt{n+1} \rfloor$ with $T(1) = 1$:

• $T(2) = T(1) + \lfloor \sqrt{2} \rfloor = 1 + 1 = 2$
• $T(3) = T(2) + \lfloor \sqrt{3} \rfloor = 2 + 1 = 3$
• $T(4) = T(3) + \lfloor \sqrt{4} \rfloor = 3 + 2 = 5$
• $T(9) = 16$ and $T(16) = 38$

Now, let us evaluate the options for $m = 4$ where $T(m^2) = T(16) = 38$:

• Option A: $\frac{4}{6}(21(4) - 39) + 4 = 34 \neq 38$
• Option B: $\frac{4}{6}(4(16) - 3(4) + 5) = \frac{2}{3}(57) = 38$ (Correct)

Method 2: Analytical Derivation

Expanding the recurrence gives:

For any integer $k$, the value of $\lfloor \sqrt{j} \rfloor = k$ for $j \in [k^2, (k+1)^2 - 1]$. The number of such terms is $(k+1)^2 - k^2 = 2k + 1$. Summing over all intervals from $k = 1$ to $m-1$, and adding the final term for $j = m^2$ (which is $m$):