Complexity & Arrays

Why a DSA track in an AI course? motivation

Because agents are made of data structures. RAG retrieval is a heap (top-k) over cosine similarities; the agent loop is a stack/queue of messages; tool dispatch is a hash map; a dependency-aware DevOps plan is a graph with a topological sort; re-ranking is sorting; chunk lookup is binary search. Knowing the structure — and its cost — is the difference between an agent that scales to a million documents and one that times out on a thousand. This track makes those choices deliberate.

1 · Big-O, Θ and Ω — the language of cost basic

Start with a story you've probably lived. You write a function. On your laptop, with 50 test rows, it returns before your finger leaves the Enter key. You ship it. Three months later, with 200,000 real rows, the same function takes 40 seconds and users are filing tickets. The code never changed — the input did. Big-O is the tool that would have warned you on day one.

Here's the whole idea in one question: when the input doubles, what happens to the work? That's it. You're not measuring seconds (those change with your CPU, your other tabs, the weather) — you're describing the shape of the growth.

• Work stays flat when the input grows → O(1) ("constant")
• Work doubles when the input doubles → O(n) ("linear")
• Work quadruples when the input doubles → O(n²) ("quadratic")

Now the formal version, which will make sense because you have the intuition: Big-O describes how the number of operations grows as the input size n grows. We drop constants and lower-order terms because we care about the shape of the growth, not the exact count. 3n + 7 and 100n are both O(n) — double n and each roughly doubles, so they scale linearly. (Yes, 100n is slower in practice — but Big-O is about how it scales, and both scale as a straight line.)

There are only about six growth shapes you meet in practice. Read this table not as a list to memorize but as a ladder of pain — each row is dramatically worse than the one above it once n gets large. The middle column ("n=1000 does ~") is the one to feel: it's roughly how many operations you'd do on a thousand-item input.

Before the numbers, see the shapes. The picture below plots work (up) against input size (right) for the common classes — the whole point of Big-O is which curve you are riding.

Let's make each row concrete, because the names mean nothing until you attach them to a feeling:

• O(1) — constant. The work doesn't care how big the input is. Grabbing list[500] takes the same time whether the list has 1,000 items or 10 million (you'll see why in §4 — it's pure address arithmetic). This is the gold standard: free at any scale.
• O(log n) — logarithmic. Every step throws away half the remaining work. That's why it barely grows: going from 1,000 to 1,000,000 items only takes ~10 more steps. Think "find a name in a phone book by always opening to the middle." Anywhere you see halving, you're in log-land — and that's almost as good as constant.
• O(n) — linear. You touch each item a fixed number of times. Double the input, double the work — a straight, predictable line. Most honest "look at everything once" code lives here, and for most jobs it's perfectly fine.
• O(n log n) — linearithmic. A linear pass, but each item pays a small log n tax. This is the speed limit for comparison sorting — no general sort can beat it — so when you call sorted(), this is what you're paying. Only a hair worse than linear; totally acceptable.
• O(n²) — quadratic. Here's where it hurts. For each item you do work proportional to every other item — the classic "loop inside a loop." At n=1,000 that's a million operations; at n=10,000 it's a hundred million. This is the single most common cause of "it worked in testing, it died in production." Section 2 is all about spotting it.
• O(2ⁿ) — exponential. Adding one element doubles the total work. This falls off a cliff almost immediately — n=60 is already more operations than there are seconds since the Big Bang. If your solution is exponential, you don't optimize it, you redesign it (that's what dynamic programming in D10–D11 is for).

Why we're allowed to throw away the details. You'll notice we said 3n + 7 is "just" O(n) — we dropped the × 3 and the + 7. That feels like cheating, so here's the justification: as n grows huge, the fastest-growing term drowns out everything else. Compare n² against 100n: at n=10 the 100n looks bigger (1,000 vs 100), but by n=1,000 the n² has pulled far ahead (1,000,000 vs 100,000) and it never looks back. Big-O deliberately ignores the small stuff because it's answering one question only: which term wins as the input explodes? Constants matter for tuning; the growth class matters for whether your program survives at all.

One more turn of that screw, because it trips people up. Take searching for a value by scanning a list. If you're lucky, it's the very first item — one check, done. If you're unlucky, it's last (or absent) — n checks. So the same algorithm is Ω(1) in the best case and O(n) in the worst. That's not a contradiction — they're describing different scenarios. When an interviewer or a design doc asks "what's the complexity?", they almost always mean the worst case (the O), because that's the one that decides whether your system falls over under load. Best-case numbers make for nice slides and terrible capacity plans.

2 · Counting operations — deriving the class basic → intermediate

In §1 we learned the vocabulary of cost. Now the practical skill: looking at a piece of code and naming its Big-O. The good news is you don't guess and you don't need a maths degree — you count, using two rules that cover almost everything you'll write.

Rule 1 — sequential steps add, and the biggest wins. If your function does one loop over n items and then, separately, another loop over n items, that's n + n = 2n operations. Two things happen: we add them (because they run one after the other), and then we drop the constant, so 2n is just O(n). More usefully: if a function does an O(n) scan and an O(n²) nested loop, the total is n + n² → O(n²). The slowest part dominates, so find the worst thing your code does and that's usually your answer.

Rule 2 — nested loops multiply. This is the one that bites. A loop inside a loop doesn't add, it multiplies: for each of the n outer passes you pay for a full n inner passes, so n × n = O(n²). Three levels deep is O(n³). The word that decides it is "inside": loops side by side add (cheap), loops nested multiply (expensive). When you review code for performance, your eye should go straight to the indentation — a loop nested in a loop is the first thing to check.

The diagram below makes the multiply-vs-add rule visual: one loop is a row of work, a nested loop is the whole grid.

python# O(n): one loop over n items
def total(nums):
    s = 0                      # O(1)
    for x in nums:            # runs n times ...
        s += x                 # ... each O(1)  -> n * O(1) = O(n)
    return s                   # O(1)   total: O(n)

# O(n^2): a loop inside a loop
def has_duplicate(nums):
    for i in range(len(nums)):       # n times
        for j in range(i+1, len(nums)): # ~n times  -> n*n = O(n^2)
            if nums[i] == nums[j]:
                return True
    return False

# O(n): same job, using a set (we'll build sets from scratch in D3)
def has_duplicate_fast(nums):
    seen = set()
    for x in nums:                  # n times
        if x in seen:                 # set membership is O(1) avg
            return True
        seen.add(x)
    return False

The two duplicate-finders return the same answer, but on 10,000 items the first does ~50 million comparisons and the second does ~10,000. Same output, different data structure, 5000× fewer operations. That is the entire point of this track.

3 · Space complexity intermediate

So far we've counted time — operations. But there's a second bill, and beginners almost always forget it until it crashes something: memory. A function can be beautifully fast and still blow up your process because it quietly built a copy of a huge input. Space complexity is the same Big-O idea pointed at a different resource: how much extra memory does this code allocate as the input n grows?

The word "extra" is the key, and it catches people out. We do not count the input itself — you were handed that. We count only what the algorithm allocates on top of it. Two examples to anchor it:

• A loop that scans a million-item list keeping a single running max uses O(1) extra space — one variable, no matter the input size. The million items were already there; you added nothing.
• A list comprehension that builds a new million-item list uses O(n) extra space — your memory footprint grows one-for-one with the input.

Why care, concretely? An agent holding a long conversation, or a RAG system loading an embedding matrix, is often memory-bound before it's time-bound — it runs out of RAM long before it runs out of patience. Knowing whether your approach is O(1) or O(n) in space is what decides whether a job fits on the machine you have. The diagram contrasts the two directly.

python# O(1) extra space: reuses a few variables regardless of input size
def max_val(nums):
    best = nums[0]
    for x in nums:
        if x > best: best = x
    return best              # space: O(1)

# O(n) extra space: builds a new list as big as the input
def doubled(nums):
    return [x*2 for x in nums]   # space: O(n)

# The generator version is O(1) space — it yields, storing nothing (see P6)
def doubled_lazy(nums):
    for x in nums:
        yield x*2              # space: O(1) — one item at a time

4 · Arrays and Python's list basic → intermediate

We've talked about cost in the abstract. Now we meet the structure that everything in this track is built on — the array — and you'll finally see why some operations are free and others are secretly expensive. Every complexity claim from here on comes back to how arrays physically sit in memory.

Picture computer memory as one enormous street of numbered houses. An array is a run of houses right next to each other, all the same size. That "same size, side by side" detail is the whole magic: to find element i, the computer doesn't walk down the street counting — it does one sum, base + i × slotsize, and jumps straight to the door. One multiply, one add, done. That is why list[i] is O(1) — instant whether the list holds ten items or ten million.

Python's list is a special kind of array called a dynamic array: an array that quietly grows itself when it runs out of room (we unpack exactly how in §5). That flexibility is why Python lists feel effortless — but it also creates a trap. The same contiguous layout that makes indexing free makes inserting at the front costly: every element behind the new one has to physically shuffle down a slot. Keep that tension in mind as you read the operation table below — fast at the end, slow at the front is the theme.

5 · Why append is O(1) "amortized" intermediate → advanced

Here's a puzzle that exposes a beautiful idea. An array is a fixed block of memory — so how can Python's list keep accepting append after append forever? And why do we call append "O(1) amortized" instead of just "O(1)"? That weasel-word "amortized" is worth understanding, because the trick behind it shows up everywhere from hash tables to database storage.

The naïve approach, and why it's a disaster. Imagine the array grew by exactly one slot each time it filled up. To add a slot you must allocate a new, slightly bigger block and copy every existing element across. Do that on every append and building an n-item list costs 1 + 2 + 3 + … + n copies — that's O(n²). Building a modest list would grind to a halt.

The fix: grow in big jumps, not tiny steps. When the array fills, Python doesn't grab one more slot — it grabs a much bigger block (roughly doubling for small lists, ~1.125× for large ones) and copies once. Now most appends land in a slot that's already sitting empty and waiting — those are true O(1). Only the occasional "we're full, time to move house" append pays the O(n) copy cost. And because each resize doubles the headroom, those expensive moves get rarer and rarer as the list grows.

That's what "amortized" means: average the rare expensive operations over the many cheap ones, and the cost per append works out to a constant. It's not that any single append is guaranteed fast — it's that across a whole sequence of appends, the total work is only about n, so the average is O(1). The diagram traces exactly this doubling; run the lab under it to watch the capacity jump with your own eyes.

pythonimport sys

lst = []
prev = -1
for i in range(17):
    cap = sys.getsizeof(lst)          # bytes the list object occupies
    if cap != prev:
        print(f"len={len(lst):2d}  bytes={cap}  <-- grew")
        prev = cap
    lst.append(i)
# You'll see the byte-size jump only at a few sizes (0, 4, 8, 16, ...),
# not on every append — that's the over-allocation making append O(1) amortized.

6 · Two pointers — O(n²) → O(n) intermediate → advanced

The last three sections (§6–§8) are your first real algorithmic techniques — named tricks that take a problem you'd naïvely solve with a slow nested loop and collapse it to a single fast pass. If §1–§5 were about measuring cost, these are about beating it. The first one is the two-pointer technique, and it's the one interviewers reach for most.

The setup. Suppose you're asked: "do two numbers in this array add up to a target?" The obvious answer is to try every pair — a loop inside a loop, O(n²). On a sorted array, there's a far smarter move. Put one finger on the smallest value (left end) and one on the largest (right end), and look at their sum:

• Sum is too small? The only way to grow it is to give up the smallest number — move the left finger right, to a bigger value.
• Sum is too big? The only way to shrink it is to give up the largest number — move the right finger left, to a smaller value.
• Sum is exactly the target? Found it.

Why this is correct, not just clever. Each comparison lets you permanently discard one number — and because the array is sorted, you can prove you never skip a valid pair (the reasoning is spelled out right after the lab). Each finger only ever moves inward, so together they take at most n steps: one linear pass, O(n) time and O(1) space, replacing the quadratic double loop. The catch — and it's essential — is that the array must be sorted first; the whole trick rides on "too small → go right, too big → go left" being reliable.

python# Brute force: check every pair -> O(n^2)
def two_sum_slow(nums, target):
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return (i, j)
    return None

# Two pointers on a SORTED array -> O(n) time, O(1) space
def two_sum_fast(nums, target):    # nums must be sorted ascending
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target:
            return (lo, hi)
        elif s < target:
            lo += 1                 # need a bigger sum -> move left pointer up
        else:
            hi -= 1                 # need a smaller sum -> move right pointer down
    return None

print(two_sum_fast([1, 3, 4, 7, 11], 10))   # (1, 3) -> 3 + 7

Why it's correct: at each step, if the sum is too small the only way to increase it is to raise the low value; if too big, lower the high value. No pair is ever wrongly skipped, and each pointer moves at most n times — so the whole scan is O(n).

7 · Sliding window advanced

The second technique attacks a whole family of questions: "what's the best/longest/largest run of consecutive items?" — the maximum sum of any 5 in a row, the longest stretch with no repeats, the shortest span that hits a threshold. The naïve approach recomputes each window from scratch, which is O(n·k) and does a mountain of duplicate work.

The insight is embarrassingly simple once you see it. When you slide a fixed-size window one step to the right, almost everything inside it is identical to a moment ago — only two things changed: one new item entered on the right, and one old item fell off the left. So don't rebuild the total. Add the entering item, subtract the leaving one, and you've updated the window in two operations flat — O(1) per slide — no matter how wide the window is.

Slide across the whole array that way and the entire scan is O(n) instead of O(n·k). The mental image is a physical window frame gliding along the array: it never lifts off and re-counts everything, it just gains one pane and loses one pane per step. That "reuse what you already computed" instinct is the heart of the technique — and, later, of dynamic programming. The diagram animates one slide; the lab computes a real max-window-sum.

pythondef max_window_sum(nums, k):
    if k > len(nums):
        raise ValueError("window bigger than array")
    window = sum(nums[:k])            # first window: O(k) once
    best = window
    for i in range(k, len(nums)):     # slide across the rest: O(n)
        window += nums[i] - nums[i-k] # add new item, drop the one leaving
        best = max(best, window)
    return best

print(max_window_sum([2, 1, 5, 1, 3, 2], 3))   # 9  (5+1+3)

8 · Prefix sums — precompute once, answer in O(1) advanced

The last technique in this chapter answers a question you'll hit constantly in analytics and data work: "what's the sum of everything between position i and position j?" — asked over and over on the same array. Answer each one by re-adding the range and you pay O(n) per question; a thousand questions is O(n × 1000) of repeated adding.

The move is to do the hard work once, up front. Build a companion array of running totals — prefix[k] holds "the sum of everything before position k." Building it is a single O(n) pass. But now watch what any range query becomes: the sum from i to j is just prefix[j+1] − prefix[i]. One subtraction. Two big running totals, subtract the earlier from the later, and the middle chunk falls out — O(1), every time, forever.

The everyday analogy: it's a bank statement. If you know your balance on March 1 and your balance on March 31, you know March's net flow by subtracting — you don't re-add every transaction. You've paid a little memory (the extra prefix array) to make thousands of future queries almost free. That "precompute-then-query" trade of space for time is a recurring pattern — it powers image processing, range queries, and the Fenwick tree you'll meet in D4. The diagram shows the two running totals being subtracted; the lab builds it in nine lines.

pythondef build_prefix(nums):
    prefix = [0] * (len(nums) + 1)     # prefix[0] = 0
    for i, x in enumerate(nums):
        prefix[i+1] = prefix[i] + x     # running total
    return prefix

def range_sum(prefix, i, j):          # sum of nums[i..j] inclusive
    return prefix[j+1] - prefix[i]      # O(1) per query

nums = [3, 1, 4, 1, 5, 9]
p = build_prefix(nums)
print(range_sum(p, 1, 3))              # 6  (1+4+1)
print(range_sum(p, 0, 5))              # 23 (whole array)

Exercises advanced

🎯 Interview practice interview

The interview questions this topic gets asked — worked, with code. For the full pattern catalog see D8 · Big Tech DSA patterns.

pythondef max_subarray(nums):
    best = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)   # extend or restart
        best = max(best, cur)
    return best

pythondef move_zeroes(nums):
    w = 0
    for x in nums:
        if x != 0:
            nums[w] = x; w += 1
    for i in range(w, len(nums)):
        nums[i] = 0

Checkpoint — you can move on when you can… advanced

def ops(n):
    a = b = c = 0
    for _ in range(n):              # (a) O(n)
        a += 1
    for i in range(n):              # (b) O(n^2)
        for j in range(n):
            b += 1
    k = n
    while k > 1:                     # (c) O(log n) -- halves each step
        k //= 2
        c += 1
    return a, b, c

print(ops(8))    # (8, 64, 3)  -> n, n^2, log2(n)

def two_sum_slow(nums, target):        # O(n^2) time, O(1) space
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

def two_sum(nums, target):             # O(n) time, O(n) space
    seen = {}                          # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i

print(two_sum([2, 7, 11, 15], 9))      # [0, 1]
print(two_sum_slow([3, 2, 4], 6))      # [1, 2]

def pair_sum_sorted(nums, target):     # O(n) time, O(1) space
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target:
            return [lo, hi]
        if s < target:
            lo += 1                     # need a bigger sum
        else:
            hi -= 1                     # need a smaller sum
    return None

print(pair_sum_sorted([1, 2, 4, 7, 11, 15], 15))   # [3, 4] -> 4+11

def length_of_longest(s):              # O(n) time, O(min(n,alphabet)) space
    last = {}                          # char -> last index seen
    start = best = 0
    for i, ch in enumerate(s):
        if ch in last and last[ch] >= start:
            start = last[ch] + 1       # shrink window past the repeat
        last[ch] = i
        best = max(best, i - start + 1)
    return best

print(length_of_longest("abcabcbb"))   # 3  ("abc")
print(length_of_longest("bbbbb"))      # 1
print(length_of_longest("pwwkew"))     # 3  ("wke")

class RangeSum:                        # build O(n), query O(1)
    def __init__(self, nums):
        self.pre = [0]
        for x in nums:
            self.pre.append(self.pre[-1] + x)
    def query(self, i, j):             # inclusive sum nums[i..j]
        return self.pre[j + 1] - self.pre[i]

rs = RangeSum([3, 1, 4, 1, 5, 9, 2, 6])
print(rs.query(2, 5))                  # 4+1+5+9 = 19
print(rs.query(0, 7))                  # 31

from collections import defaultdict

def subarray_sum(nums, k):             # O(n) time, O(n) space
    count = 0
    running = 0
    seen = defaultdict(int)
    seen[0] = 1                        # empty prefix sums to 0
    for x in nums:
        running += x
        count += seen[running - k]     # prefixes that make (running - prefix)=k
        seen[running] += 1
    return count

print(subarray_sum([1, 1, 1], 2))          # 2
print(subarray_sum([3, 4, -7, 1, 3, 3, 1, -4], 7))  # 4

Knowledge check check yourself