Time Complexity — previous-year questions

This session applies the loop-counting method to real previous-year questions (GATE and company-test style). Attempt each one before watching the worked solution — a wrong first attempt teaches more than a watched answer.

How to attack a complexity PYQ

1. Rewrite the loops as counts. For each loop, write exactly how many times it runs in terms of n (not “roughly n” — the exact sum).
2. Sum or multiply. Sequential blocks add; nested blocks multiply. For dependent bounds, write the summation (Σ over the outer variable) and simplify.
3. Keep the dominant term. Only then convert to Big-O / Θ. Doing this last avoids the classic error of dropping terms too early.

Patterns these questions recycle

• Inner loop bound depending on the outer variable (j <= i) → arithmetic series → Θ(n²).
• Outer loop multiplicative, inner loop linear → Θ(n log n) — and its reverse, which is also Θ(n log n) but derived differently.
• Loops whose variable is squared or square-rooted (i*i < n) → Θ(√n).
• A loop that shrinks the problem by a constant fraction each pass → logarithmic, the bridge to recurrence relations later in the course.

Exam discipline

• GATE frequently asks for Θ (tight bound), not just O — an answer that’s a valid upper bound can still be the wrong option.
• Constants and lower-order terms never matter for the answer, but the case (best/worst/average) named in the question always does.

Mark the lesson complete once you can solve each question in the video without pausing — that’s the bar the actual exam sets.