Consider the following recurrence relation: T(n) = cases n\,T(n) + n & for n ≥ 1, \\ 1 & for n = 1. cases Which one of the following options is CORRECT?

GATE CSE 2024 Session 1 Q42: Solve T(n) = √n T(√n) + n

Consider the following recurrence relation:

$T(n) = \begin{cases} \sqrt{n}\,T(\sqrt{n}) + n & \text{for } n \ge 1, \\ 1 & \text{for } n = 1. \end{cases}$

Which one of the following options is CORRECT?

Try it: multiple choice: exactly one correct option

Wrong answer costs 2/3 mark in GATE.

Show answer and explanation

Answer: A (official GATE 2024 final answer key)

Concept used: Divide by $n$ to get a recurrence in $S(n) = T(n)/n$ , then substitute $n = 2^m$ .

First step: $T(n)/n = T(\sqrt{n})/\sqrt{n} + 1$ , so $S(n) = S(\sqrt{n}) + 1$ , which unrolls $\log\log n$ times.

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

Source: official GATE 2024 Session 1 CS question paper and final answer key, organised by IISc Bangalore. Question paper · Answer key