Day 2: Big-O Notation

DAY 2 / 30 · WEEK 1

Goal of the day

• Understand that Big-O describes how work grows as input size grows — not how many seconds something takes.
• Recognize the 6 complexity classes you’ll see constantly: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ).
• Be able to look at a code snippet and say its time complexity by counting loops and halving patterns.

Concept

Big-O answers one question: “If the input doubles, how much more work do I do?” — not “how many seconds does this take on my laptop.” A hotel concierge who helps you in the same amount of time no matter how full the hotel is: that’s O(1). Checking every guest’s name against a printed list, one by one: double the guests, double the work — that’s O(n). Repeatedly cutting a phone book in half to find a name: double the guests, and you only need one more step — that’s O(log n). Comparing every guest to every other guest (say, “who shares your birthday?”): double the guests, and the work goes up by 4× — that’s O(n²). Sorting the guest list efficiently — a linear scan repeated roughly log n times — is O(n log n). And trying every possible subset of guests for a group photo (2 choices — in or out — per guest) is O(2ⁿ): it’s fine for 5 guests and completely impossible for 500.

We drop constants and lower-order terms (O(2n + 5) is just written O(n)) because Big-O is about the shape of the growth curve for large n, not the exact count. A slightly slower O(n) algorithm always beats an O(n²) one eventually, no matter what the constants are — that crossover is what Big-O predicts.

Diagram

Operations vs. input size (n), for the 6 complexity classes you’ll see over and over in this course. The chart is capped at 50 operations — O(n²) and O(2ⁿ) don’t actually flatten out, they just fly straight past the top edge and get clipped there. In reality they keep climbing far higher.

The code

Here’s what each complexity class typically looks like in real code:

// O(1) — constant. No loop, work doesn't depend on input size.
function first(arr) { return arr[0]; }

// O(log n) — logarithmic. Each step cuts the problem in half.
// (Full binary search implementation on Day 12.)
function halvingSteps(n) {
  let steps = 0;
  while (n > 1) { n = Math.floor(n / 2); steps++; }
  return steps;
}

// O(n) — linear. One loop over the input.
function sum(arr) {
  let total = 0;
  for (const x of arr) total += x;
  return total;
}

// O(n log n) — linearithmic. A linear amount of work, log n times.
// JS's built-in sort uses an algorithm in this class (Merge Sort on Day 10).
function sorted(arr) { return [...arr].sort((a, b) => a - b); }

// O(n²) — quadratic. A loop inside a loop over the same input.
function countPairs(arr) {
  let count = 0;
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      count++;
    }
  }
  return count;
}

// O(2ⁿ) — exponential. Every call branches into 2 more calls.
// (Full breakdown of why this is O(2ⁿ) on Day 9 and Day 25.)
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

Line by line:

• first(arr) — returns immediately. No loop, so no dependency on arr’s size. O(1).
• halvingSteps(n) — each iteration divides n by 2. The loop runs about log₂(n) times before n shrinks to 1. O(log n).
• sum(arr) — one pass, one operation per element. O(n).
• sorted(arr) — copies the array (O(n)) then sorts it. Efficient sorting algorithms do a linear amount of work at each of roughly log n “levels” — that combination is O(n log n), which we’ll build by hand on Day 10.
• countPairs(arr) — for every element, scan the rest of the array. Loop inside a loop, both bounded by arr.length. O(n²).
• fib(n) — every call (except the base cases) makes 2 more calls. That branching factor of 2, repeated n times deep, gives O(2ⁿ) total calls.

Dry run: countPairs([10, 20, 30, 40])

4 elements, so we expect 4 × 3 / 2 = 6 pairs — let’s trace it:

Step	i	j	count
1	0	1	1
2	0	2	2
3	0	3	3
4	1	2	4
5	1	3	5
6	2	3	6

The inner loop shrinks each time, but the total number of comparisons still grows with the square of the input size — that’s the signature of O(n²).

Complexity

Class	Name	Ops at n=10	Ops at n=20	Typical space	Why
O(1)	Constant	1	1	O(1)	Same work regardless of input size.
O(log n)	Logarithmic	~3	~4	O(1)	Each step cuts the remaining problem in half.
O(n)	Linear	10	20	O(1)	Work grows exactly with input size.
O(n log n)	Linearithmic	~33	~86	O(n)*	A linear pass, repeated log n times — efficient sorting.
O(n²)	Quadratic	100	400	O(1)	Nested loop — every element checked against every other.
O(2ⁿ)	Exponential	1,024	1,048,576	O(n)†	Work doubles with every single extra input element.

Notice n=20 for O(2ⁿ): over a million operations, from an input just twice the size of n=10’s 1,024. That jump is why exponential algorithms become unusable almost immediately as input grows.
*Merge sort (Day 10) needs O(n) extra space for the merge step. †Naive recursive Fibonacci is O(2ⁿ) time, but only O(n) space — that’s the max depth of the call stack at any one moment, not the total number of calls made (more on this Day 9 and Day 25).

Interview corner

• What’s the difference between O(n) and O(n²)? Give a code example of each. O(n) is one loop over the input (e.g. summing an array); O(n²) is a loop nested inside another loop over the same input (e.g. checking every pair). Doubling the input doubles O(n)’s work but quadruples O(n²)’s.

  ↳ Common follow-up: “Can you turn an O(n²) pair-checking algorithm into O(n)?” — often yes, by trading space for time with a hash set (we build this exact pattern on Day 6).

• Why do we drop constants, like writing O(2n) as just O(n)? Big-O describes the growth shape for large n, not an exact operation count. The constant factor matters for real-world speed, but it doesn’t change which algorithm wins as n keeps growing — an O(n) algorithm eventually beats an O(n²) one no matter the constants.

  ⚠ Trap: “eventually” is doing real work in that sentence — for small, bounded inputs a “worse” Big-O algorithm with tiny constants can genuinely be faster in practice. Don’t over-optimize Big-O at the cost of readability for code that only ever runs on small n.

• What’s the difference between best, average, and worst case complexity? Best case: the luckiest input (e.g. searching and the target is first). Worst case: the unluckiest (target is last, or missing entirely). Interviewers almost always want worst case unless they say otherwise — it’s the guarantee you can actually rely on.

• Can an algorithm have different time and space complexity? Yes, and interviewers love asking for both. Memoized recursive Fibonacci is O(n) time but also O(n) space (the cache); the iterative version is O(n) time and O(1) space (two variables).

  ⚠ Trap: by convention, space complexity usually excludes the input itself (and sometimes the output) — it’s about extra space your algorithm allocates. Say this explicitly in an interview; it removes ambiguity about what you’re counting.

How to talk through it out loud: name the complexity as soon as you spot the shape (“this is two nested loops over n, so O(n²)”), then immediately say whether that’s good enough: “given the constraints say n ≤ 10⁴, O(n²) is 10⁸ operations — that’s borderline, I’d look for an O(n log n) or O(n) approach.” Tying Big-O to the actual input size given in the problem is what separates “I memorized the term” from “I can use it.”

Practice problems

These are less about the “trick” and more about noticing the brute-force complexity, then asking “can I do better?” — the core interview skill for today.

1. Contains Duplicate — Easy

Given an array of integers, return true if any value appears at least twice.

Hint: The brute-force way compares every pair — what’s its complexity? A Set lets you check “have I seen this before?” in O(1), which changes the total complexity.

Solution:

// Brute force: O(n²) time, O(1) space — compare every pair.
// Better: O(n) time, O(n) space — trade space for time.
function containsDuplicate(nums) {
  const seen = new Set();
  for (const n of nums) {
    if (seen.has(n)) return true;
    seen.add(n);
  }
  return false;
}

2. Best Time to Buy and Sell Stock — Easy

Given daily stock prices, find the maximum profit from buying on one day and selling on a later day. Return 0 if no profit is possible.

Hint: Brute force checks every buy/sell pair — O(n²). You only need to track the lowest price seen so far as you scan once, left to right.

Solution:

// Brute force: O(n²) — check every (buy day, sell day) pair.
// Better: O(n) — one pass, track the minimum price so far.
function maxProfit(prices) {
  let minPrice = Infinity;
  let best = 0;
  for (const price of prices) {
    minPrice = Math.min(minPrice, price);
    best = Math.max(best, price - minPrice);
  }
  return best;
}

3. Two Sum — Easy

Given an array of integers and a target, return the indices of the two numbers that add up to the target.

Hint: Brute force checks every pair — O(n²). For today, just identify that complexity and sketch the idea of trading space for time again. We’ll build the full O(n) hash-map solution properly on Day 6.

Solution:

// Brute force: O(n²) time, O(1) space — the version to write TODAY.
// (The O(n) hash-map version is Day 6's lesson — don't worry about it yet.)
function twoSum(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) return [i, j];
    }
  }
  return [];
}

Quiz

Quiz: 1. A single loop over an array of size n has what time complexity?

O(n)

One loop that touches each element once is the textbook definition of O(n).

Quiz: 2. Two nested loops, both over the same array of size n, give what time complexity?

O(n²)

A loop inside a loop, both over the same input, multiplies to n × n = n².

Quiz: 3. Which grows faster as n increases: O(n log n) or O(n²)?

O(n²)

O(n²) always grows faster than O(n log n) — there’s no crossover, check the chart above.

Quiz: 4. O(2n + 5) is usually simplified to which of these?

O(n)

Constants are dropped in Big-O — O(2n + 5) describes the same growth shape as O(n).

Quiz: 5. Binary search cuts the search space in half every step. What’s its time complexity?

O(log n)

Cutting the search space in half every step is exactly what makes binary search O(log n).