Big-O & Arrays

0How to use this week

Reading is not learning. This page is built to be used, not skimmed.

• Play every interactive. The two widgets below aren't decoration — clicking them is how the intuition sticks.
• Try each problem before revealing. Spend five real minutes stuck. Being stuck and then seeing the trick is worth ten passive read-throughs.
• Say the complexity out loud. Every time you finish a solution, finish the sentence: "…so that's O(?) time and O(?) space." The interview tests whether you can say it.
• Then go practise. The lesson teaches the model; spend the rest of the week's hours doing easy array problems until the patterns are automatic.

1Big-O — the cost of code

Big-O answers one question: as the input grows, how fast does the work grow?

It is not a stopwatch. "My laptop runs it in 3 milliseconds" tells an interviewer nothing — a faster machine changes that number, but it doesn't change whether your algorithm scales. Big-O throws away the hardware and the constants and keeps only the shape of the growth. That shape is the difference between code that handles a billion users and code that melts at a thousand.

Reading complexity straight off the code

You don't compute Big-O with math — you read it off the structure. The loops tell you almost everything:

# O(1) — constant. No loop over the input; one step regardless of size.
x = nums[0]

# O(n) — linear. One pass: work grows in lockstep with n.
for v in nums:
    total += v

# O(n^2) — quadratic. A loop inside a loop over the same input.
for i in nums:
    for j in nums:
        print(i, j)

# O(log n) — logarithmic. The input is HALVED each step (n -> n/2 -> n/4 ...).
while n > 1:
    n = n // 2

The complexity ladder — feel the difference

These shapes look similar near the origin and then diverge violently. Toggle each curve and read what it actually costs at n = one million — the gap between O(n) and O(n²) is the whole game.

Two rules that simplify everything

• Drop the constants. O(2n + 5) is just O(n). Big-O cares about growth shape, not exact counts — doubling the work doesn't change how it scales.
• Keep only the biggest term. O(n² + n) is O(n²). For large n, the n² utterly dominates the n, so the small term is noise.

Space complexity — the same idea, for memory

Big-O also measures extra memory your algorithm allocates as the input grows (not counting the input itself). Solving a problem with a couple of variables is O(1) space; building a new list or a hash set of size n is O(n) space. Interviewers grade both — the best answers state the time/space trade-off you chose.

Quick drill — classify the complexity

Pick the tightest Big-O. (Answers reveal instantly, with the why.)

for v in nums:
    if v == target:
        return True
return False

for i in range(len(nums)):
    for j in range(len(nums)):
        if nums[i] + nums[j] == target:
            return (i, j)

while n > 1:
    n = n // 2
    steps += 1

2Arrays — the workhorse data structure

An array is a row of values laid out back-to-back in memory. That one physical fact explains all of its speed and all of its slowness.

Because the elements are contiguous and all the same size, the computer can find element i with pure arithmetic: address = start + i × element_size. No searching. That's why reading or writing by index is O(1) — instant, at any size. But it's also why inserting or deleting in the middle is O(n): to make room (or close a gap) every element after the spot has to physically shuffle over.

See it — why index is free but insert-at-front isn't

Each box is a memory slot with its address. Try the three operations and watch the cost.

* "Amortised O(1)": a dynamic array (Python list, Swift Array, Java ArrayList) occasionally runs out of room and copies everything to a bigger block — an O(n) hiccup. But that's rare enough that averaged over many appends, each one is effectively O(1). You can say "amortised constant" and sound exactly right.

Strings are arrays too

A string is essentially an array of characters, so the same costs apply: indexing a character is O(1), scanning is O(n). The one gotcha: in many languages (Python, Java, Swift) strings are immutable — every "edit" actually builds a new string. So building a result character-by-character with s = s + c inside a loop is a sneaky O(n²). The fix is to collect pieces in a list and join once at the end.

Operation cost cheat-sheet

Three array techniques you'll use constantly

• One pass + a running value. Sweep once, carrying a "best/min/sum so far". Turns many O(n²) brute forces into O(n). (Problems 1 & 2 below.)
• Two pointers / a write pointer. Use indices that move through the array to rearrange it in place — O(1) extra space. (Problem 3.)
• Remember what you've seen. Store seen values in a hash set for O(1) "have I seen this?" checks — trading space for speed. (Problem 4 — and all of next week.)

3Worked problems

The fun part. Read the problem, actually try it for a few minutes, peek at the hint if stuck, then check the solution.

def max_profit(prices):
    min_price = float('inf')   # cheapest day we could have bought
    best = 0                   # best profit found so far
    for p in prices:
        min_price = min(min_price, p)     # update cheapest buy
        best = max(best, p - min_price)   # best sale if we sell today
    return best

def max_subarray(nums):
    best = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)   # extend the run, or start over at x
        best = max(best, cur)   # remember the best run we've seen
    return best

def move_zeroes(nums):
    w = 0                      # next position to write a non-zero
    for x in nums:             # read pointer sweeps the array
        if x != 0:
            nums[w] = x
            w += 1
    while w < len(nums):       # fill the tail with zeros
        nums[w] = 0
        w += 1

def contains_duplicate(nums):
    seen = set()
    for x in nums:
        if x in seen:        # O(1) membership check
            return True
        seen.add(x)
    return False

4Self-check quiz

Five questions. If you can ace these, the week's concepts are yours. The score tracks at the bottom.

5You've finished Week 1 when you can…

Tick these off honestly. They're the bar for moving on — and they save in your browser.

• Look at any loop and state its Big-O, and justify it in one sentence.
• Explain the difference between O(n) and O(n²) using the "if the input doubles…" test.
• Say why array indexing is O(1) but inserting at the front is O(n).
• Explain "amortised O(1)" for appending to a dynamic array.
• Solve an easy array problem in one pass and state both its time and space complexity out loud.
• Score 5/5 on the quiz above without peeking.
• Spend the rest of the week's hours grinding easy array/string problems until the one-pass pattern is automatic.