Consider an algorithm with . What is the time complexity?

Master Theorem: . . Since (Case 2), .

GATE CSE · Algorithms

Asymptotic Analysis – GATE CSE AlgorithmsPractice Questions & PYQs

Generate diverse GATE-level questions covering time and space complexity, Big-O, Theta, Omega notations, best/worst/average cases, and comparison of growth rates.

103 questions · 0 PYQs · 3 AI practice · GATE CSE 2027

📘Asymptotic AnalysisNotes & FormulasQuick concept summary before you practiseRead notes →

Q101MediumMCQ

Which of the following is NOT true for asymptotic notations?

🚀 Solve in Practice Mode

📖 Explanation

B is FALSE in general. Counterexample: $f(n) = n$ , $g(n) = 2n$ ; then $f(n)=O(g(n))$ , but $2^n \neq O(2^{2n}) = O(4^n)$ - actually here it is true. Better: $f(n)=2n$ , $g(n)=n$ : $2n=O(n)$ is false, but $2^{2n} \neq O(2^n)$ since $4^n/2^n = 2^n \to \infty$ . The statement B is NOT always true.

Q102MediumNAT

Let $T(n) = 4T(n/2) + cn$ for constant $c > 0$ , with $T(1) = 1$ . Using the Master Theorem, what is the value of $\log_b a$ (i.e., $\log_2 4$ )?

🚀 Solve in Practice Mode

📖 Explanation

$a = 4,\ b = 2$ . $\log_b a = \log_2 4 = 2$ . Since $f(n) = cn = O(n^{2-\epsilon})$ for $\epsilon = 1$ (Case 1), $T(n) = \Theta(n^2)$ .

Q103MediumMCQ

Consider an algorithm with $T(n) = 2T(n/4) + \sqrt{n}$ . What is the time complexity?

🚀 Solve in Practice Mode

📖 Explanation

Master Theorem: $a=2, b=4, f(n)=\sqrt{n}=n^{0.5}$ . $n^{\log_4 2} = n^{0.5}$ . Since $f(n) = \Theta(n^{\log_b a})$ (Case 2), $T(n) = \Theta(n^{0.5} \log n) = \Theta(\sqrt{n} \log n)$ .

Want unlimited AI-generated Asymptotic Analysis questions?

Start practising for free →