Reading Big O, Omega and Theta

O(f(n)) is an upper bound: beyond some input size, the cost grows no faster than f(n), up to a constant factor. It is a ceiling, not a promise of exactness.

• Ω(f(n)) is a lower bound — it grows at least this fast.
• Θ(f(n)) is both: the cost grows exactly at this rate.

In practice everyone writes O for everything, and interviewers mean Θ when they ask "what is the complexity?". Say Θ when you can be precise; nobody will object.

The three rules of simplification

Drop constants. O(3n) is O(n). O(n/2) is O(n).

Drop lower-order terms. O(n² + n + 100) is O(n²).

Multiply for nesting, add for sequence.

// Sequence: O(n) then O(n)  →  O(n + n) = O(n)
items.forEach(step);
items.forEach(step);

// Nesting: O(n) inside O(n)  →  O(n × n) = O(n²)
items.forEach((a) => items.forEach((b) => step(a, b)));

Two traps worth naming

Different inputs need different letters. Iterating an n-element list against an m-element list is O(n × m), not O(n²). Interviewers listen for this.

Built-ins are not free. includes, indexOf, filter, and spreading an array are each O(n). This looks linear and is quadratic:

const unique = [];
for (const item of items) {
  if (!unique.includes(item)) unique.push(item);  // O(n) inside O(n)
}

String concatenation in a loop has the same problem in languages where strings are immutable — building a result by += repeatedly can copy the whole string each time.

Saying it out loud

"This is O(n log n) time because we sort once, and O(n) space because of the map." That single sentence — a cost, a reason, for both time and space — is the answer the question is looking for.