Time and space complexity interview questions, with answers

The questions, with answers

1. 1.What does Big-O notation actually say, and what does it leave out?

   Big-O describes how the running time (or memory) grows as the input grows, in the limit, ignoring constant factors and lower-order terms. O(n) means the time is at most proportional to n for large n; it does not say the algorithm is fast, only how its cost scales. It leaves out constants — an O(n) algorithm that does a thousand operations per element is slower than an O(n log n) one for any n you will meet — and it describes an upper bound, so technically a linear algorithm is also O(n²). In interviews, "the complexity" means the tightest bound in the worst case unless you say otherwise; Big-Θ is the tight bound and Big-Ω the lower bound, and knowing the three exist is usually enough.

2. 2.What are the common complexity classes, in order, with an example of each?

   From fastest-growing input tolerance to slowest: O(1), indexing an array or a hash lookup; O(log n), binary search or a balanced tree lookup; O(n), scanning a list or a single loop; O(n log n), merge sort, heap sort and the best comparison sorts; O(n²), nested loops over the same input — bubble sort, checking every pair; O(2^n), trying every subset, naive recursive Fibonacci; O(n!), trying every permutation. The practical scale for an interview: a modern machine does roughly 10^8 simple operations a second, so n² is fine for n up to about 10^4, n log n handles 10^6 comfortably, and anything exponential is only for n around 20.

3. 3.How do you analyse nested loops and sequential loops?

   Sequential blocks add; nested blocks multiply; then keep the dominant term and drop constants. Two separate loops of n each are n + n = 2n, which is O(n). A loop of n with a loop of n inside it is n × n = O(n²). Put the two together — two single loops followed by a double loop — and the total is 2n + n², which is O(n²), because n² dominates. The common mistake is to write O(n² + n) or O(3n); the notation exists to throw those details away. One more shape: an inner loop that runs i times for i from 1 to n does 1 + 2 + ... + n = n(n+1)/2 steps, which is still O(n²) — a half-triangle is a constant factor, not a different class.

4. 4.Where does O(log n) come from?

   From halving or doubling. A loop whose variable doubles each time — for (i = 1; i < n; i *= 2) — runs about log2(n) times, because that is how many doublings it takes to reach n; the same for a loop that halves. Binary search halves the remaining range each step; a balanced binary tree has log n levels; a heap's sift-down walks one path of log n height. The base of the logarithm does not matter to Big-O, since log2(n) and log10(n) differ by a constant factor. When a log n loop sits inside an n loop — for each element, binary search — you multiply: O(n log n). Recognising "the problem size divides by a constant each step" is the whole skill.

   for (int i = 1; i < n; i = i * 2) {   // 1, 2, 4, 8, ... : about log2(n) iterations
       // O(1) work
   }

5. 5.How do you find the complexity of a recursive algorithm?

   Write its recurrence, then solve it — usually by recognising the shape. T(n) = T(n-1) + O(1), one call on a problem one smaller, is O(n): factorial, a linear scan done recursively. T(n) = T(n/2) + O(1), one call on half the problem, is O(log n): binary search. T(n) = 2T(n/2) + O(n), two halves plus linear work to combine, is O(n log n): merge sort. T(n) = 2T(n-1) + O(1), two calls each one smaller, is O(2^n): naive subset generation, and Fibonacci is close to it. The Master Theorem covers the T(n) = aT(n/b) + f(n) family generally, but interviewers mostly want you to name which of these four shapes you are looking at and why.

6. 6.How do you count space complexity, and does the recursion stack count?

   Space complexity counts the extra memory an algorithm allocates beyond its input, as a function of input size — and yes, the call stack counts. An in-place iterative reversal of an array is O(1) extra space; a recursive version that goes n levels deep is O(n) because of n live stack frames, even though it allocates nothing on the heap. Merge sort needs an O(n) temporary array plus O(log n) stack; quicksort is O(log n) stack on average but O(n) in its worst case. When an interviewer asks for "space", say whether you are counting the input, and separate heap allocations from stack depth; that precision is usually the difference between a partial and a full answer.

7. 7.What is amortised complexity, and how is it different from average case?

   Amortised complexity is the average cost per operation over a worst-case sequence of operations — a guarantee, not a probability. Appending to a dynamic array is the standard example: most appends are O(1), and occasionally one triggers an O(n) copy into a doubled array, but across n appends the copies total O(n), so each append is O(1) amortised. Average-case complexity, by contrast, averages over random inputs — quicksort is O(n log n) on average but O(n²) for an adversarial input, and no sequence argument rescues it. Hash tables use both words: O(1) average per lookup (assuming a good hash), and O(1) amortised per insertion (accounting for resizes). Say which one you mean.

8. 8.Why is accessing an array index O(1) but a linked list index O(n)?

   An array is a contiguous block, so the address of element i is the base address plus i times the element size — one multiplication and one addition, regardless of n. A linked list's nodes are wherever the allocator put them, connected only by pointers, so reaching element i means following i pointers from the head. The same contiguity is why arrays are cache-friendly and why binary search needs an array: it must jump to the middle in O(1). The trade-off runs the other way for insertion — inserting into the middle of an array shifts everything after it, O(n), while a list inserts in O(1) once you are at the spot. Choosing the structure is choosing which operation you want to be cheap.

How the diagnostic asks it

One question from the DSA bank, exactly as a sitting would show it. The bank has 3 on time & space complexity analysis and 60 across DSA.