GATE CS 2024 (Forenoon) — Question 42

AlgorithmsAsymptotic Analysis (O, Omega, Theta Complexities)MCQ2 marks · −2/3 if wrongHard

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?
  1. A
    \( T(n) = \Theta(n \log \log n) \)
  2. B
    \( T(n) = \Theta(n \log n) \)
  3. C
    \( T(n) = \Theta(n^2 \log n) \)
  4. D
    \( T(n) = \Theta(n^2 \log \log n) \)
Practise the full 2024-FN paper
Challenge a friend: WhatsApp Telegram
From RENYXERAThis week's 10-question challengeSame 10 past-GATE questions for everyone this week — see where you stand.
Practise more on Asymptotic Analysis (O, Omega, Theta Complexities)Timed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group