Question

Let T(n) be a function defined by the recurrence T(n) = 2T(n/2) + $\sqrt{n}$ for n $\ge$ 2 and T(1) = 1. Which of the following statement is TRUE?

• A. T(n) = $\ominus$(n log n)
• B. T(n) = $\ominus$(n)
• C. T(n) = $\ominus$$\sqrt{n}$
• D. T(n) = $\ominus$(log n)

Answer 1

The correct option is B T(n) = $\ominus$(n)

T(n) = 2T(n/2) + $\sqrt{n}$
By substitution method T(n) = $\ominus$(n).
T(n) = 2. T(n/2) + $\sqrt{n}$ ...(1)
= 2[2 . T(n/4) + $\sqrt{n/2}$] + $\sqrt{n}$
= $2^2$ . T(n/$2^2$) + $\sqrt{n}$(1 + $\sqrt{2}$) ...(2)
= $2^3$ . T(n/$2^3$) + $\sqrt{n}$(1 + $\sqrt{2}$ + 2) ...(3)

= $2^k$ . T(n/$2^k$) + $\sqrt{n}$(${\sum }^{k=1}i=0$) = $\ominus$(n)