GATE CS 2021 (Forenoon) — Question 40

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

Consider the following recurrence relation:
\[ T(n) = \begin{cases} T\left(\left\lceil \frac{n}{2} \right\rceil\right) + T\left(\left\lfloor \frac{2n}{5} \right\rfloor\right) + 7n & \text{if } n > 0 \\ 1 & \text{if } n = 0 \end{cases} \]
Which one of the following options is correct?
  1. A
    \(T(n) = \theta(n^{5/2})\)
  2. B
    \(T(n) = \theta(n \log n)\)
  3. C
    \(T(n) = \theta(n)\)
  4. D
    \(T(n) = \theta((\log n)^{5/2})\)
Practise the full 2021-FN paper
Challenge a friend: WhatsApp Telegram
From RENYXERAFree All-India Mock — every SundayA full GATE CS paper, exactly 180 minutes, ranked across India with your GATE score.
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