GATE CS 2021 (Afternoon) — Question 49

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

For constants \(a \geq 1\) and \(b > 1\), consider the following recurrence defined on the non-negative integers:
\[ T(n) = a \cdot T\left(\left\lceil \frac{n}{b} \right\rceil\right) + f(n) \]
Which one of the following options is correct about the recurrence \(T(n)\)?
  1. A
    If \(f(n)\) is \(n \log_2(n)\), then \(T(n)\) is \(\Theta(n \log_2(n))\).
  2. B
    If \(f(n)\) is \(\frac{n}{\log_2(n)}\), then \(T(n)\) is \(\Theta(\log_2(n))\).
  3. C
    If \(f(n)\) is \(O(n^{\log_b(a) - \epsilon})\) for some \(\epsilon > 0\), then \(T(n)\) is \(\Theta(n^{\log_b(a)})\).
  4. D
    If \(f(n)\) is \(\Theta(n^{\log_b(a)})\), then \(T(n)\) is \(\Theta(n^{\log_b(a)})\).
Practise the full 2021-AN paper
Challenge a friend: WhatsApp Telegram
From RENYXERAWhat rank do your marks get?GATE score, likely All-India Rank and qualifying marks for your category.
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