Question

When n = $2^{2k}$ for some k $\ge$ 0, the recurrence relation T(n) = $\sqrt{2}$ T(n/2) + $\sqrt{n}$, T(1) = 1 evalutes to:

• A. $\sqrt{n}$(log n + 1)
• B. n log $\sqrt{n}$
• C. $\sqrt{n}$log$\sqrt{n}$
• D. $\sqrt{n}$log n

Answer 1

The correct option is A $\sqrt{n}$(log n + 1)

T(n) = $\sqrt{2}$ . T(n/2) + $\sqrt{n}$ ...(1)
= $\sqrt{2}$ [$\sqrt{2}$ . T(n/4) + $\sqrt{n/2}$ + $\sqrt{n}$]
= ($\sqrt{2}$)${}^2$ . T(n/2${}^2$) + 2$\sqrt{n}$ ....(2)
= ($\sqrt{2}$)${}^3$ . T(n/2${}^3$) + 3$\sqrt{n}$ ....(3)
= ($\sqrt{2}$)${}^{2k}$) . T(n/2${}^{2k}$)) + 2k$\sqrt{n}$
= ($\sqrt{2}$)${}^{logn}$ . 1 + loh n . $\sqrt{n}$ [$\because$ put 2K = log n]
= $\sqrt{n}$ + log n . $\sqrt{n}$
= $\sqrt{n}$ (log n + 1)