Question 1

What is Big O notation actually telling you?

Accepted Answer

Big O describes **how an algorithm's cost grows as the input grows**. It is a statement about the shape of the growth curve, not about speed in any absolute sense.

**What it deliberately ignores:**

**Constant factors.** An algorithm taking `1000n` steps and one taking `2n` steps are both **O(n)**. In practice the first is 500 times slower.

**Lower-order terms.** `n² + 500n + 9000` is **O(n²)**, because for large enough n the quadratic term dominates everything else.

**Hardware, language and implementation quality.**

This is why Big O tells you almost nothing about small inputs and almost everything about large ones. A well-implemented O(n²) algorithm frequently beats an O(n log n) one for small collections — which is why real sorting implementations switch to insertion sort below a threshold.

**The common classes**, best to worst:

**O(1)** constant — hash map lookup, array index.
**O(log n)** logarithmic — binary search. Doubling the input adds one step.
**O(n)** linear — scanning a list.
**O(n log n)** — efficient sorting. This is the proven lower bound for comparison sorts.
**O(n²)** quadratic — nested loops over the same data. Fine at n=100, catastrophic at n=100,000.
**O(2ⁿ)** exponential — naive recursive subset problems. Unusable beyond trivial inputs.

**Why it matters practically:** the difference between O(n) and O(n²) is what separates code that works in testing from code that collapses in production. Ten thousand records is 10⁸ operations quadratically.

**Beyond time:** Big O also describes **space** complexity, and the two often trade against each other.

**Best, average and worst cases differ.** Quicksort is O(n log n) average and O(n²) worst. Hash lookups are O(1) average and O(n) in the pathological case.

**Measure before optimising** — asymptotic analysis identifies scaling risks, not current bottlenecks.

Question 2

What is a hash table, and why is lookup constant time?

Accepted Answer

A structure that turns a key into an array index by computing a number from it, so finding an item takes roughly the same time whether the table holds ten entries or ten million. The mechanism. A

Question 3

When does a database index hurt performance?

Accepted Answer

Indexes speed up reads by maintaining an ordered structure alongside the table, and that structure has to be kept correct on every write. Every insert, update and delete must update every affected

Question 4

When should you use an array rather than a linked list?

Accepted Answer

Almost always — and the textbook answer, which favours linked lists for insertion and deletion, is misleading on modern hardware because it ignores how memory actually behaves. The theoretical

Question 5

Why is my PostgreSQL query still slow after adding an index?

Accepted Answer

An index existing and an index being used are different things. The planner chooses a strategy based on its cost estimates, and it will ignore an index whenever it believes a sequential scan will be

Question 6

How do you find a performance bottleneck?

Accepted Answer

By measuring before changing anything, because intuition about where time goes is reliably wrong — and the great majority of wasted optimisation effort comes from skipping that step. The order that

Question 7

What is recursion, and when should you use it?

Accepted Answer

A function that calls itself, solving a problem by reducing it to a smaller version of the same problem until it reaches a case simple enough to answer directly. The two required parts. A base case,

Related Questions