Algorithms | Analysis of Algorithms (Recurrences) | Question 4

25 June 2025

Suppose T(n) = 2T(n/2) + n, T(0) = T(1) = 1
Which one of the following is false. ( GATE CS 2005)
a) T(n) = O(n^2)
b) T(n) = $\theta$ (nLogn)
c) T(n) = $\Omega$ (n^2)
d) T(n) = O(nLogn)

(A) A
(B) B
(C) C
(D) D

Answer: (C)
Explanation: See question 4 of https://www.geeksforgeeks.org/data-structures-and-algorithms-set-23/ for explanation.
Quiz of this Question

Whether you’re preparing for your first job interview or aiming to upskill in this ever-evolving tech landscape, neveropen Courses are your key to success. We provide top-quality content at affordable prices, all geared towards accelerating your growth in a time-bound manner. Join the millions we’ve already empowered, and we’re here to do the same for you. Don’t miss out – check it out now!