Analyzing Simple Algorithms

Analyzing Simple Algorithms

Before you can compare two solutions to a problem, you need a way to talk about how fast or hungry for memory each one is — without running them. Timing code with a stopwatch is unreliable: results depend on your CPU, your language, the compiler, and what else the machine is doing. Algorithm analysis strips all that away. The core idea is simple: count how the amount of work grows as the input grows, and ignore everything that doesn't affect that growth. If doubling the input roughly doubles the work, that's fundamentally different from doubling the input quadrupling the work — and that difference, not the raw seconds, is what decides whether your program survives a million users.

The precise definition

We measure an algorithm by its running time as a function of input size n — usually counting a representative basic operation (a comparison, an addition, an array access) rather than nanoseconds. We then describe how that count grows using asymptotic notation, which captures behaviour as n gets large and discards constant factors and lower-order terms.

• Big-O (O) — an upper bound: the work grows no faster than this. This is the one interviewers mean 90% of the time.
• Big-Omega (Ω) — a lower bound: the work grows at least this fast.
• Big-Theta (Θ) — a tight bound: upper and lower bounds match.

Two rules do most of the work. Drop constants: O(3n) and O(n/2) are both O(n). Keep only the dominant term: O(n2 + n) is just O(n2), because for large n the n2 term swamps the rest. Formally, f(n) = O(g(n)) means there exist constants c > 0 and n0 such that f(n) ≤ c·g(n) for all n ≥ n0.

Worked example: counting operations

Take a function that, for each element in an array of size n, checks it against every other element (a naive duplicate finder):

• for i in 0..n-1:   for j in 0..n-1:   if a[i] == a[j] and i != j: return true

Let's count comparisons for n = 5 in the worst case (no duplicates, so it never returns early). The outer loop runs 5 times; for each, the inner loop runs 5 times. That's 5 × 5 = 25 comparisons. For n = 10 it's 100; for n = 1000 it's 1,000,000. The count is exactly n2. Even if we skip i == j, we do n(n-1) = n2 - n comparisons — but we drop the -n and any constant, so this is O(n2), called quadratic. Edge: n = 0 or n = 1 → no off-diagonal pairs; the early-return path never fires on a single-element array that cannot hold a duplicate pair.

Now contrast a single pass that sums the array: one addition per element, n operations total — O(n), linear. And a lookup like a[0] does a fixed amount of work regardless of n — O(1), constant; a hash-set membership test matches it on average — expected O(1), though its worst case degrades to O(n) under heavy collisions (see the Hash Table page). Notice how analysis lets us rank these instantly: at n = 1000, constant does ~1 op, linear does ~1000, quadratic does ~1,000,000.

Best, worst, and average case

A single algorithm can have different costs depending on the specific input, not just its size. Consider linear search for a target in an unsorted array of n items:

• Best case — target is the first element: O(1), one comparison.
• Worst case — target is last or absent: O(n), n comparisons.
• Average case — target equally likely anywhere: about n/2 comparisons, still O(n).

By default, unqualified Big-O usually refers to the worst case, because that's the guarantee you can rely on. But be explicit — some algorithms (like quicksort at O(n log n) average but O(n2) worst) live or die by which case you quote.

Pitfalls and what an interviewer probes

• Loops aren't automatically their bound. A loop that does i *= 2 runs log n times, not n times. Interviewers plant these to see if you count iterations, not lines.
• Sequential vs. nested. Two separate loops are O(n) + O(n) = O(n). A loop inside a loop is O(n) × O(n) = O(n2). Add for sequence, multiply for nesting.
• Hidden costs. Slicing an array, string concatenation in a loop, or a .contains() on a list can each be O(n) — turning an innocent-looking loop into O(n2).
• Different variables. Processing two inputs is O(n + m) or O(n·m) — collapsing them to O(n) is a classic error.
• Space too. Interviewers often follow "what's the time?" with "what's the space complexity?" — count extra memory the same way, including the recursion call stack.

When it matters + trade-offs

Analysis matters most at scale and at decision points. For n = 10, an O(n2) algorithm is fine — 100 operations is nothing, and its simplicity may beat a clever O(n log n) one. But choose that same quadratic algorithm for a million-row dataset and you've committed to a trillion operations — minutes or hours instead of milliseconds. The neighbouring classes tell the story: O(log n) barely grows (a billion items is ~30 steps), O(n) is the gold standard for "must read all input," O(n log n) is the practical ceiling for good sorting, and O(n2) and beyond signal "only for small or bounded input."

The real skill is recognising the trade-offs: a hash set can turn an O(n2) duplicate scan into O(n) time — at the cost of O(n) extra space. That time-for-space bargain is the single most common optimisation in interviews, and it only becomes visible once you can analyse both dimensions.

Key takeaways

• Count growth, not seconds. Analysis measures how work scales with n, independent of hardware — drop constants and keep only the dominant term.
• Add for sequence, multiply for nesting. Separate loops sum; nested loops multiply. This mechanical rule handles most simple algorithms.
• Always name the case. Best, worst, and average can differ; unqualified Big-O means worst case — the guarantee you can trust.
• Analyse time and space. The classic optimisation trades extra memory for speed (e.g. a hash set turning O(n2) into O(n)) — you can't spot it without measuring both.