Time Complexity Questions in GATE CSE: Reading Code Fast

Reading a code fragment for its time complexity is the single most frequent algorithm task in GATE CSE. It scores 86.5 out of 100 in the book's evidence model, the top score among algorithm concepts, and the reconstruction from public archives finds some form of it in every paper from 2010 onward. The skill is narrow and drillable: recognise the loop shape, count the executions, then name the growth rate.

Key takeaways

• Six loop shapes generate almost every past question. Learn the count each one produces, not a rule of thumb.
• The paper increasingly asks for an exact execution count as a numeric answer rather than an asymptotic class.
• Asymptotic statement sets are multiple-select with no partial credit, so one wrong tick scores zero.
• The recurring wrong answers are predictable and are built into the options on purpose.
• Space complexity appears as short statement questions about the standard sorts and recursion depth.

What the syllabus asks for

The official Algorithms line names asymptotic worst case time and space complexity. That is the whole mandate, and it is enough to support one or two items per shift. The expectation stated in the book for 2027 is one one-mark multiple choice item and possibly one two-mark numeric answer on this concept.

Analyst compilations, which are not official and differ by about 2 to 3 marks between sources, put Algorithms at roughly 8.3 marks per paper averaged across 2009 to 2026, with a reported range of 6 to 11. Complexity reading is the part of that total you can make almost automatic.

The six loop shapes

Two of these deserve working through.

Doubling outer, linear inner. Suppose the outer variable starts at 1 and doubles until it exceeds n, and the inner loop runs from 1 up to the current outer value. For n equal to 64 the outer values are 1, 2, 4, 8, 16, 32 and 64, so the statement executes 127 times. In general the sum is just under twice n, so the growth is linear even though a log appears in the structure.

Inner advancing by the outer variable. Now the outer variable runs from 1 to n and the inner loop starts at the outer value and advances by it each time. The inner loop then runs about n divided by the outer value times. Summing that over all outer values gives n times a harmonic sum, which is about n times the natural log of n. The shape looks like two nested full loops, which is why n squared is the built-in wrong answer.

The square-root shape is worth a sanity check too. If the loop condition compares the square of the variable against n and the variable increases by one each step, it runs about the square root of n times, so for n equal to one million it runs a thousand times.

The book ranks this concept alongside the other 27 algorithm concepts on the same evidence model and pairs each loop shape with practice questions covering its variants.

Counting exactly, not approximately

The format has shifted. Numeric answer questions now carry a large share of the algorithm marks, and they ask how many times a statement executes for a stated n rather than which asymptotic class the fragment belongs to. Asymptotics will not answer those.

The reliable method is mechanical. Write the outer variable's values as an explicit sequence. For each one, write the inner loop's count. Add them. If the sequence is geometric, use the closed form; if it is harmonic, sum the small number of terms the question actually needs. Never convert to big O before the arithmetic is done, because constants and off-by-one terms are exactly what the answer depends on.

A related shape asks for the value returned by a recursive function rather than its complexity. Those belong to programming rather than algorithms and are covered in the Programming and Data Structures guide, but the counting habit is the same: tabulate from the base case upward.

Asymptotic comparison

The second half of this topic is comparison rather than counting, and since multiple-select questions arrived it has become an all-or-nothing format. The facts worth memorising:

• The log of n factorial grows like n log n.
• Any power of log n is eventually smaller than any positive power of n.
• n raised to the power log n grows more slowly than two to the n. Compare their logarithms, which are the square of log n against n, and n wins.
• If f is in big O of g, then the log of f is in big O of the log of g, provided both are eventually at least 2.
• If f is in big O of g, it does not follow that two to the f is in big O of two to the g.
• Big O is an upper bound and does not imply theta. Both directions are needed for theta.

The last three lines are the ones the setters combine. A statement set typically pairs a true theorem with its false cousin, so the discipline is to test each option separately rather than pattern-match the group. Because multiple-select carries no partial credit, half-certainty is worth nothing here; the approach is set out in the exam-day time management guide.

Space complexity in one paragraph

Space questions are short and factual. Merge sort on arrays needs linear auxiliary space, and it is not in place. Quicksort needs only the recursion stack, which is logarithmic when the splits are balanced and linear in the worst case. Heapsort is in place and needs constant extra space. A recursive function's space is its maximum depth times the frame size. These turn up as one-mark statement items, often mixed with stability facts, where quicksort and heapsort are not stable and merge sort is.

Turning this into practice

Three passes work well. First, write the six loop shapes and their counts from memory until you can do it without hesitation. Second, take code fragments and compute exact counts for a specific n, checking your arithmetic rather than your instinct. Third, do mixed multiple-select sets on asymptotic statements, marking every option individually as true or false before you select anything.

Then place the topic in context. It sits at rank 24 in the wider most repeated topics ranking, the rest of the subject is mapped in Algorithms important topics, and the recurring wrong answers listed above appear again in the common mistakes guide.