Algorithm Analysis Interview Questions and Answers: Big-O, Loops and Recurrences

Algorithm analysis interviews expose a gap that complexity tables cannot fix. Remembering that binary search is logarithmic is not enough if you cannot define the input size, choose the counted operation, distinguish a tight bound from an upper bound, or defend a different choice when a constraint changes. Start with a short screening response, then earn depth by counting a dependent loop, turning a shrinking search into a recurrence, and comparing algorithms under changed constraints.

What algorithm analysis is actually measuring

Interview question: What do we mean by analysing an algorithm?

A strong short answer is: define the input size n, select a meaningful primitive operation, and describe how the operation count and auxiliary memory grow with n. Also name the case being analysed, such as best, worst, average, or amortized. Without those choices, a complexity label lacks context.

Big-O gives an asymptotic upper bound. Big-Omega gives a lower bound, and Big-Theta gives a tight bound when both match. Big-O does not itself mean worst case. A best-case running-time function can also have a Big-O bound.

For a proof, take f(n) = n log2 n + 5n against the candidate class g(n) = n log2 n. For every n >= 2 the factor log2 n is at least 1, so n <= n log2 n and therefore 5n <= 5n log2 n. Chaining those two facts gives a two-sided bound:

n log2 n <= f(n) <= n log2 n + 5n log2 n = 6n log2 n.

So f(n) is O(n log n) with c2 = 6, Omega(n log n) with c1 = 1, and therefore Theta(n log n). The threshold n0 = 2 serves both sides. At n = 2, g(n) = 2 and f(n) = 12, so 2 <= 12 <= 12. At n = 4, g(n) = 8 and f(n) = 28, so 8 <= 28 <= 48.

The choice n0 = 1 fails because g(1) = 0 while f(1) = 5, and no constant makes 5 <= c x 0. The witnesses justify discarding the lower-order 5n term.

Read complexity from changing loop bounds

Interview prompt: Count how many times the innermost statement runs.

count = 0
for (i = 1; i <= n; i = i + 1)
    for (j = 1; j <= i * i; j = j + 1)
        count = count + 1

Take the primitive operation to be the increment of count. Each inner iteration performs it once, so the final value of count is also the execution total.

Do not multiply the visible loop counts mechanically. The inner bound is i * i, not n, so it changes on every outer pass. For n = 6 the outer values i = 1, 2, 3, 4, 5, 6 make the inner body run 1, 4, 9, 16, 25, 36 times.

The total work is a sum of squares:

1 + 4 + 9 + 16 + 25 + 36 = 91, and in general 1^2 + 2^2 + ... + n^2 = n(n + 1)(2n + 1)/6.

That closed form expands to (2n^3 + 3n^2 + n)/6, a cubic, so the algorithm takes Theta(n^3) time and Theta(1) auxiliary space. Doubling the input confirms the class: T(6) = 91, T(12) = 650, and T(24) = 4900, multiplying by about 7.1 and then 7.5 as the ratio climbs toward the cubic factor 8.

Counting visible loops instead of work gives n x n = 36 at n = 6, not the actual 91 operations. Because the inner limit is i x i, two loop statements still produce Theta(n^3) work.

Convert a shrinking search into a recurrence

Interview question: Why is binary search logarithmic?

Consider the sorted array [3, 7, 11, 18, 25, 31, 44, 58], indexed from 0 to 7, and search for 58 using the floor midpoint.

1. The candidate set has size 8. Index 3 contains 18, so search indices 4 to 7.

2. The set has size 4. Index 5 contains 31, so search indices 6 to 7.

3. The set has size 2. Index 6 contains 44, so search index 7.

4. The set has size 1. Index 7 contains 58, so the search succeeds.

The worst-case recurrence for this eight-element trace is:

T(8) = T(4) + 1 = T(2) + 2 = T(1) + 3 = 4.

Each unsuccessful comparison discards the lower half in this trace, leaving four, then two, then one candidates. The recurrence records one comparison plus the cost of a problem half as large.

In general, T(n) = T(n/2) + 1 = Theta(log n). Four is the exact comparison count for this input, while Theta(log n) describes how the count grows. An iterative implementation uses Theta(1) auxiliary space.

Choose an algorithm by constraints, not by slogan

Interview prompt: Detect whether [7, 2, 9, 4, 2, 5, 8, 1] contains a duplicate.

Three approaches can be defensible:

• Compare every pair. In the no-duplicate or late-duplicate worst case, eight elements require up to 8 x 7 / 2 = 28 equality checks. This takes Theta(n^2) time and Theta(1) auxiliary space.

• Sort, then scan adjacent values. An appropriate comparison sort takes Theta(n log n) time here. Its auxiliary-space cost depends on the chosen sorting algorithm. The Sorting Algorithms: Complexity and Comparison guide develops that choice.

• Maintain a hash set. Check 7, 2, 9, 4, inserting each. Membership check number 5 sees the second 2, after four distinct values have been stored. Under standard hash-table assumptions, this is expected Theta(n) time and Theta(n) auxiliary space. It does not promise constant time for every individual lookup.

If extra space is forbidden, pairwise comparison or in-place sorting may become preferable. If input order must remain unchanged, do not sort the original array. This example owns the cost comparison for duplicate detection. The earlier DSA Interview Follow-Up Questions: Optimise Brute Force Step by Step owns the full baseline-to-optimised coding drill on pair sum.

Follow-up traps that reveal memorised answers

Does two loops mean quadratic? No. Loop bounds can depend on each other, in either direction. The earlier nested loops execute their body 91 times for n = 6 and take Theta(n^3) time.

Does Big-O mean worst case? No. Big-O is a mathematical upper bound. Worst case describes which inputs a running-time function covers.

Can we ignore the base of a logarithm? For an asymptotic class, yes, because changing the base introduces a constant factor. For an exact comparison count, no. The binary-search trace above makes exactly four comparisons.

What belongs in auxiliary space? Count extra working memory, including a recursion stack or data structure such as a hash set. Do not count storage already occupied by the input.

Average-case analysis averages cost across an input distribution. Amortized analysis spreads occasional expensive operations across a sequence, such as when some dynamic-array appends trigger resizing while the sequence remains cheap overall. For retrieval practice on these distinctions, try Time Complexity MCQs: 12 Solved on Big-O.

Give a short answer first, then earn the deeper answer

Interview depth varies by role, team, and hiring drive. A screening prompt may stop after the correct definition and complexity. A deeper discussion may ask for a trace, a proof, an alternative, the space cost, an edge case, or a new constraint. Treat service and product interviews as a depth spectrum, not as fixed company rules.

Use this four-part response at the whiteboard:

1. Define n and the operation you are counting.

2. Trace the work on the given input values.

3. State the input case, time bound, and auxiliary-space bound.

4. Discuss the next-best approach when a constraint changes.

That structure works for the sum-of-squares loop, the shrinking binary search, and the duplicate check. It turns a memorised statement into a defensible answer. Start short, then add evidence as the interviewer probes.

The short version and the next practice step

• Define the input size and counted operation.

• Count the actual work instead of judging visible loops.

• Name the best, worst, average, or amortized case.

• Give a tight bound where the evidence supports one.

• State the time-space tradeoff and how constraints change it.

For guided interview-focused study, continue with the DSA using Java Placement Preparation Course, or browse the wider Coding & Skills route.