Time complexity is the most reliably tested area of Algorithms, and the questions cluster into three habits: ordering functions by growth rate, counting the work inside nested loops, and solving recurrences with the Master Theorem. Get those three fluent and a large slice of the Algorithms marks is yours. Below are 12 solved MCQs from KnowledgeGate's published question bank, all previous-year GATE problems with the year marked. Attempt each before the explanation, which is short by design. A note on the deep links: each of these questions is carried as a solved GATE PYQ inside the course, so every one links its exact page. If a step feels shaky, the full theory sits in the Algorithms learn module.
Asymptotic notation and growth rates
Q1. Let S be a sorted array of n integers. T(n) is the time of the most efficient algorithm to decide whether two elements of S have a sum less than 1000. Which is true? *(GATE 2000)*
(a) T(n) is O(1)
(b) n < T(n) < n log n
(c) n log n < T(n) < C(n, 2)
(d) T(n) = C(n, 2)
Answer: (a) T(n) is O(1). Because S is sorted, the two smallest elements are S[0] and S[1], and their sum is the smallest possible pair sum. So you only check whether S[0] + S[1] < 1000, a constant amount of work independent of n. The sorted-ness collapses what looks like a pair-search into two array reads (see the solved page).
Q2. Let f(n) = n^2 log n and g(n) = n (log n)^10. Which statement is correct? *(GATE 2001)*
(a) f(n) = O(g(n)) and g(n) is not O(f(n))
(b) f(n) is not O(g(n)) and g(n) = O(f(n))
(c) f(n) = O(g(n)) and g(n) = O(f(n))
(d) neither is O of the other
Answer: (b). Take the ratio f(n)/g(n) = (n^2 log n) / (n (log n)^10) = n / (log n)^9. A polynomial in n grows faster than any fixed power of log n, so this ratio tends to infinity. That means f grows strictly faster, so g(n) = O(f(n)) but f(n) is not O(g(n)). Polynomial beats polylog every time (see the solved page).
Q3. Arrange in increasing order of asymptotic growth: f1(n) = 2^n, f2(n) = n^(3/2), f3(n) = n log n, f4(n) = n^(log n). *(GATE 2011)*
(a) f3, f2, f4, f1
(b) f3, f2, f1, f4
(c) f2, f3, f1, f4
(d) f2, f3, f4, f1
Answer: (a) f3, f2, f4, f1. Rank by growth: n log n is barely above linear, then n^1.5 is a genuine polynomial. Next is n^(log n), which equals e^(log^2 n), super-polynomial yet still sub-exponential. Finally 2^n is pure exponential and dominates all. The trap is n^(log n): it beats every fixed polynomial but loses to 2^n (see the solved page).
Analysing loops
Q4. For the loop for (i = n, j = 0; i > 0; i /= 2, j += i); what is the order of val(j), the value of j after the loop? *(GATE 2006)*
(a) Theta(log n)
(b) Theta(sqrt n)
(c) Theta(n)
(d) Theta(n log n)
Answer: (c) Theta(n). Each iteration halves i and adds it to j, so j accumulates n + n/2 + n/4 + ... down to 1. That geometric series is bounded above by 2n and below by its first term n, so j is both O(n) and Omega(n), hence Theta(n). The number of iterations is logarithmic, but the value accumulated is linear, and the question asks about the value (see the solved page).
Q5. Consider a function that returns an integer k, with k starting at 0. The outer loop runs i from n/2 up to n; for each i the inner loop runs j from 2 up to n, doubling j each time (j = 2*j); and the loop body executes k = k + n/2. What value does the function return? *(GATE 2013)*
(a) Theta(n^2)
(b) Theta(n^2 log n)
(c) Theta(n^3)
(d) Theta(n^3 log n)
Answer: (b) Theta(n^2 log n). Track how much is added to k. The outer loop runs about n/2 times, and for each of those the inner loop doubles j from 2 up to n, which is Theta(log n) iterations. Every inner step adds n/2 to k, so the total is (n/2) times (log n) times (n/2), which is Theta(n^2 log n). The value returned is driven by the per-step increment, not just the loop counts (see the solved page).
Q6. For the nested loop with i from 1 to n and inner j from 1 stepping by i while j < n, the time complexity is *(GATE 2017)*
(a) Theta(n sqrt n)
(b) Theta(n^2)
(c) Theta(n log n)
(d) Theta(n^2 log n)
Answer: (c) Theta(n log n). For a fixed i the inner loop runs about n/i times, so the total work is n times the sum of 1/i for i from 1 to n. That sum is the harmonic series, which is Theta(log n). Multiplying gives Theta(n log n). Recognising the harmonic series inside a variable-step loop is the whole move here (see the solved page).
Recurrences and the Master Theorem
Q7. For T(1) = 1 and T(n) = 2 T(floor(n/2)) + sqrt(n) for n >= 2, which is true? *(GATE 1997)*
(a) T(n) = O(sqrt n)
(b) T(n) = O(n)
(c) T(n) = O(log n)
(d) none of the above
Answer: (b) T(n) = O(n). In Master Theorem form a = 2, b = 2, so n^(log_b a) = n. The extra work sqrt(n) is polynomially smaller than n, which is Case 1, giving T(n) = Theta(n). So O(n) is the correct bound. The floor does not affect the asymptotic order (see the solved page).
Q8. The running time satisfies T(n) = n for n <= 3, and T(n) = T(n/3) + c n otherwise. The complexity is *(GATE 2009)*
(a) Theta(n)
(b) Theta(n log n)
(c) Theta(n^2)
(d) Theta(n^2 log n)
Answer: (a) Theta(n). Here a = 1, b = 3, so n^(log_b a) = n^0 = 1. The extra work c n is polynomially larger than 1, which is Case 3, and the regularity condition holds since a f(n/b) = c n/3 stays below f(n). So T(n) = Theta(n), dominated by the top-level work, not the recursion (see the solved page).
Q9. Procedure A(n) returns 1 if n <= 2, else returns A(sqrt(n)). The running time is best described by *(GATE 2002)*
(a) O(n)
(b) O(log n)
(c) O(log log n)
(d) O(1)
Answer: (c) O(log log n). The recurrence is T(n) = T(sqrt n) + O(1). Substitute n = 2^m, so S(m) = T(2^m) satisfies S(m) = S(m/2) + O(1), which solves to O(log m). Since m = log n, the running time is O(log log n). This substitution, replacing n by 2^m, is the standard tool for square-root recurrences (see the solved page).
Q10. The recurrence capturing the optimal execution time of the Towers of Hanoi with n discs is *(GATE 2012)*
(a) T(n) = 2 T(n-2) + 2
(b) T(n) = 2 T(n-1) + n
(c) T(n) = 2 T(n/2) + 1
(d) T(n) = 2 T(n-1) + 1
Answer: (d) T(n) = 2 T(n-1) + 1. The algorithm moves the top n-1 discs to the spare peg (cost T(n-1)), moves the largest disc to the target (cost 1), then moves the n-1 discs back onto it (cost T(n-1) again). Adding these gives T(n) = 2 T(n-1) + 1, which unrolls to the familiar 2^n - 1 moves (see the solved page).
Divide and conquer: counting operations
Q11. For public-key cryptography, what is the tightest upper bound on the number of multiplications to compute b^n mod m? *(GATE 2007)*
(a) O(log n)
(b) O(sqrt n)
(c) O(n / log n)
(d) O(n)
Answer: (a) O(log n). Use exponentiation by repeated squaring. Write n in binary with about log n bits; for each bit you square once, and for each 1-bit you do one extra multiply. Both counts are bounded by the number of bits, so the total is O(log n) multiplications, not the naive O(n) (see the solved page).
Q12. If n is a power of 2, the minimum number of multiplications needed to compute a^n is *(GATE 1999)*
(a) log2 n
(b) sqrt n
(c) n - 1
(d) n
Answer: (a) log2 n. Let n = 2^k. Compute a^2 by one multiply, then square repeatedly: a^2, a^4, a^8, and so on. After k squarings you have a^(2^k) = a^n, so exactly k = log2 n multiplications. This is the same repeated-squaring idea as the modular exponentiation above, stripped to its core (see the solved page).
How time complexity is examined
The set mirrors the exam: asymptotic notation and growth-rate ordering (Q1 to Q3), counting work inside loops including the geometric and harmonic patterns (Q4 to Q6), recurrences solved by the Master Theorem and substitution (Q7 to Q10), and divide-and-conquer operation counts like repeated squaring (Q11 to Q12). Most errors come from ignoring the per-iteration work in a loop, or from misreading which Master Theorem case applies.
Rebuild the fundamentals and drill the full previous-year sets in the Algorithms learn module, then see the analysis applied to real algorithms in our sorting algorithms comparison and complexity breakdown. GATE aspirants get the complete Algorithms sequence inside GATE Guidance by Sanchit Sir, and the GATE CS Exam category shows where it sits in the syllabus. Solve, review the ones you missed, and return a week later; the second pass is where the marks lock in.
