GATE CS 1997 Q4.6 — Asymptotic Worst Case Time and Space Complexity

Let $T(n)$ be the function defined by $T(1) =1, \: T(n) = 2T (\lfloor \frac{n}{2} \rfloor ) + \sqrt{n}$ for $n \geq 2$ .

Which of the following statements is true?

View worked solution

Answer: B

To find the asymptotic tight bound for the recurrence relation, we can apply the Master Theorem for divide-and-conquer recurrences of the form:

T(n) = aT\left(\frac{n}{b}\right) + f(n)

For the given recurrence:

T(n) = 2T\left(\left\lfloor \frac{n}{2} \right\rfloor\right) + \sqrt{n}

We identify the parameters:

Now, we compare $f(n)$ with $n^{\log_b a}$ :

n^{\log_b a} = n^{\log_2 2} = n^1 = n

Since $f(n) = O(n^{1 - \epsilon})$ for $\epsilon = 0.5 > 0$ , we are in Case 1 of the Master Theorem.

Therefore, the solution to the recurrence is:

T(n) = \Theta(n^{\log_b a}) = \Theta(n)

Since $T(n) = \Theta(n)$ , it is also true that $T(n) = O(n)$ .

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Related questions