Time complexity comes up in GATE year after year, 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 most time-complexity questions become mechanical rather than clever. Every question below is a GATE previous-year MCQ, spanning 1997 to 2017. Attempt each one before you read the answer, then follow its link to the same question worked out step by step inside the course. 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 (work through the full solution).
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 (work through the full solution).
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 (work through the full solution).
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). Read the update order carefully: i is halved first, and only then is the new i added to j. So n itself is never added, and j accumulates n/2 + n/4 + n/8 and so on down to 1. That geometric series sums to just under n (run it with n = 1024 and the loop leaves j = 1023), and it is at least n/2, 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 full worked solution).
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 full worked solution).
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 full worked solution).
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, and the floor does not affect the asymptotic order. All three cases, with the boundary recurrences the theorem cannot handle, are worked out in Master Theorem for GATE (open the full solution to this recurrence step by step).
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 (open the full solution).
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 (open the full solution).
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 (open the full solution).
Exponentiation by squaring: counting multiplications
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 complete solution).
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 complete solution).
How time complexity is examined
GATE keeps returning to the same four moves: asymptotic notation and growth-rate ordering (Q1 to Q3), counting the work inside loops where the geometric and harmonic patterns hide (Q4 to Q6), recurrences solved by the Master Theorem and by substitution (Q7 to Q10), and multiplication counts under repeated squaring (Q11 to Q12). Most errors come from ignoring the per-iteration work in a loop, exactly the trap in Q4, 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.
