beginnerintermediateadvanced

Data Structures & Algorithms · Section 2

Big-O and Complexity Analysis

Level: beginner
Read: 95 min
Concepts: 17

The vocabulary for talking about how much work an algorithm does as its input grows — worst-case growth rather than exact speed, how loops and recursion are analyzed, the seven complexity classes worth knowing cold, and the Python-specific operation costs that decide which data structure is fast enough.

What is true here

Big-O describes worst-case growth as n gets large, never how many seconds a specific run takes.
Sequential loops add their costs; a loop nested inside another multiplies them.
Memorize the order: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), O(n!).
in on a list is O(n); in on a dict/set is O(1) average — the single most common Python performance fix.
Building a string with += inside a loop is O(n²); ''.join() is O(n).

What you will be able to do

State whether a piece of code is O(1), O(n), or O(n²) by reading its loop structure
Turn a stated input constraint into which complexity classes are ruled out
Name the Python operations that are O(1) versus O(n) on a list, and O(1) average on a dict/set
Replace a += string-building loop and a list-membership check with their O(n) equivalents

Concepts

The vocabulary and reasoning tools for naming an algorithm's cost.

What Big-O measures

standardbeginner

Big-O describes how the WORST-CASE amount of work grows as input size n grows — not how many seconds a specific run takes. Two functions with the same Big-O can run at very different speeds, and still both be "O(n)".

Think of it as

Big-O is a shape of growth, not a stopwatch reading. A search that always checks every element does the same number of comparisons regardless of what hardware runs it — that comparison COUNT, and how it scales with n, is what O(n) describes. Wall-clock time also depends on hardware, language overhead, and what else is running, none of which Big-O claims to measure.

python

def linear_search_counted(items, target):
    count = 0
    for item in items:
        count += 1
        if item == target:
            return count
    return count

What we're doing: Confirm that a search checking every element does work that scales linearly with n, regardless of n's actual size.

what_big_o_measures.pypython

def linear_search_counted(items, target):
    count = 0
    for item in items:
        count += 1
        if item == target:
            return count
    return count


for n in (10, 100, 1000):
    items = list(range(n))
    print(n, linear_search_counted(items, -1))

8: target=-1 never appears, so the search always runs to completion — the comparison count equals n exactly, every time, which is what "O(n)" is claiming: the work scales in direct proportion to n.

Output

10 10
100 100
1000 1000

Why this works: The comparison count tracks n exactly (10, 100, 1000) — not some fixed number, and not a number that depends on the computer running it. That is the growth relationship Big-O names; how many real seconds each of those three runs took is a separate question Big-O does not answer.

Remember: O(n) is a claim about how work SCALES with n, in the worst case — never a claim about how many seconds a run takes.

Big-O vs Big-Theta vs Big-Omega

referencebeginner

Big-O is an upper bound ("at most this much work"), Big-Omega is a lower bound ("at least this much"), and Big-Theta is both at once ("exactly this, up to a constant"). Everyday usage says "O(n)" for all three loosely — precise usage keeps them separate.

Remember: O is a ceiling, Ω is a floor, Θ is both at once — everyday "Big-O" talk usually means Θ without saying so.

Time complexity vs space complexity

standardbeginner

Time complexity counts how many operations an algorithm does; space complexity counts how much EXTRA memory it uses beyond the input itself. The two are independent — a solution can trade one for the other.

Think of it as

Two correct solutions to the same problem can sit at different points on a time/space trade-off: one spends extra memory (a set) to run faster, another spends more time (sorting in place) to use less extra memory. Neither is "the" right answer — it depends on which resource is scarcer for the problem at hand.

What we're doing: Compare two correct duplicate-detection solutions: one spends extra space for O(n) time, the other spends time to use O(1) extra space.

time_vs_space.pypython

def has_duplicate_extra_space(nums):
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False


def has_duplicate_no_extra_space(nums):
    nums_sorted = sorted(nums)
    for i in range(len(nums_sorted) - 1):
        if nums_sorted[i] == nums_sorted[i + 1]:
            return True
    return False


data = [4, 2, 7, 2, 9]
print(has_duplicate_extra_space(data), has_duplicate_no_extra_space(data))

1: This version is O(n) time but O(n) extra space — the set can hold up to every element.
9: sorted() does allocate a new list (not truly O(1) space in CPython), but the SCANNING step itself needs no extra structure — the point stands at the design level: no per-element extra structure is kept, at the cost of O(n log n) time instead of O(n).

Output

True True

Why this works: Both functions give the correct answer for the same input, from two different points on the time/space trade-off — the set-based version is faster (O(n) vs O(n log n)) at the cost of extra memory; the sort-based version uses less per-element extra structure at the cost of the sort itself.

Contains DuplicateeasyLeetCode
Solve it both ways from this concept's own example — a set (O(n) time, O(n) space) and a sort-then-scan (O(n log n) time, ~O(1) extra space) — and compare.
Two SumeasyLeetCode
The brute force is O(n^2) time, O(1) space; the hash-map version is O(n) time, O(n) space — the same trade-off, in the most-asked interview problem there is.

Remember: Time and space complexity are two separate bills — a faster solution often pays for its speed in extra memory, and that trade is a real design decision, not a side effect.

Dropping constants and lower-order terms

standardbeginner

Big-O keeps only the fastest-growing term and drops multipliers: 3n + 5 becomes O(n), and n^2 + n becomes O(n^2). What survives is whichever term dominates once n is large.

Think of it as

As n grows very large, a constant multiplier (3x the loops) and a smaller added term (+5, or +n next to n^2) matter less and less compared to the dominant term. Big-O intentionally ignores exactly the details that stop mattering at scale, keeping only the term that predicts behavior for large n.

What we're doing: Confirm that three separate full passes over an input is still O(n), not O(3n) as a distinct class.

dropping_constants.pypython

def three_passes(items):
    total = 0
    for x in items:
        total += x
    for x in items:
        total += x
    for x in items:
        total += x
    return total


print(three_passes([1, 2, 3]))

2: Three separate loops over the same n-length input do 3n total iterations — but 3n and n belong to the same growth class, so this is still described as O(n), not "O(3n)".

Output

Why this works: The output (18 = (1+2+3) * 3) confirms the function runs correctly across three full passes; the complexity claim is separate from the output — 3n operations is still O(n) because Big-O compares growth SHAPE, and 3n and n have the same shape as n scales up.

Remember: A constant multiplier or a smaller added term never changes the Big-O class — 3n is O(n), and n^2 + n is O(n^2).

Analyzing loops (single, nested, sequential)

corebeginner

A single loop over n items is O(n). Two loops one after another (sequential) is still O(n) — they add. A loop inside a loop (nested), each running n times, multiplies to O(n^2).

Think of it as

Sequential loops ADD their costs: O(n) + O(n) is O(n), because the total work is still directly proportional to n. Nested loops MULTIPLY: for every one of n outer steps, the inner loop runs n more steps, so the total is n times n. Mixing these two up — treating two sequential loops as if they were nested — is one of the most common complexity-analysis mistakes.

What we're doing: Count the actual number of iterations for a nested loop versus two sequential loops over the same input.

analyzing_loops.pypython

def count_pairs_nested(items):
    count = 0
    for i in items:
        for j in items:
            count += 1
    return count


def count_two_sequential(items):
    count = 0
    for i in items:
        count += 1
    for j in items:
        count += 1
    return count


items = list(range(4))
print(count_pairs_nested(items), count_two_sequential(items))

3: The outer loop runs 4 times.
4: For EACH of those 4 outer steps, the inner loop runs 4 more times — 4 * 4 = 16 total, confirming the multiply rule.
11: This loop runs 4 times, once.
13: This second loop also runs 4 times — sequentially AFTER the first, so the total is 4 + 4 = 8, not 4 * 4.

Output

16 8

Why this works: Both functions loop over the same 4-item input, but the nested version does 16 iterations (4*4) while the sequential version does 8 (4+4) — the exact numbers confirm nested loops multiply and sequential loops add, not the other way around.

Treating two sequential O(n) loops as if they were nested

Wrong

python

# "two loops over the input, so this must be O(n^2)" — WRONG reasoning
def count_two_sequential(items):
    count = 0
    for i in items:
        count += 1
    for j in items:
        count += 1
    return count

Better

python

# two SEPARATE, SEQUENTIAL passes — costs add, not multiply: O(n) + O(n) = O(n)
def count_two_sequential(items):
    count = 0
    for i in items:
        count += 1
    for j in items:
        count += 1
    return count

What you see: The code is identical either way — the bug here is purely in the ANALYSIS: calling this O(n^2) because 'there are two loops', when it is actually O(n).

Why: Multiplying is only correct when one loop is NESTED INSIDE another, so the inner loop's full cost is paid once per outer iteration. Two loops that run one after the other each pay their own cost exactly once — 4 + 4 = 8, not 4 * 4 = 16, which the traced counts above confirm directly.

Sequential adds; nested multiplies

Measured with count_two_sequential/count_pairs_nested above, not estimated — the nested curve visibly bends upward while sequential stays a straight line.

Measured iteration count, same input size, sequential vs nested

Measured iteration count, same input size, sequential vs nested
n	Sequential: O(n) + O(n)	Nested: O(n) * O(n)
2	4	4
4	8	16
8	16	64
16	32	256

Together

python

for n in (2, 4, 8, 16):
    items = list(range(n))
    print(n, count_two_sequential(items), count_pairs_nested(items))
# 2 4 4 / 4 8 16 / 8 16 64 / 16 32 256

Remember: Loops one after another ADD their costs; a loop nested inside another MULTIPLIES — mixing these up is the single most common complexity-analysis mistake.

Analyzing recursion via recurrence relations

standardintermediate

A recursive function's cost can be written as a recurrence: T(n) equals the cost of one call's own work, plus the cost of whatever it recurses into. T(n) = T(n-1) + O(1) unrolls to O(n) total calls.

Think of it as

Informally, write down what one call does BESIDES recursing (its own work), and what it recurses into. A function that does O(1) work and calls itself once on a slightly smaller input, T(n) = T(n-1) + O(1), makes n calls total before reaching the base case — O(n). A function that calls itself TWICE per call, T(n) = 2*T(n-1) + O(1), branches into roughly 2^n calls — the same shape naive Fibonacci has, and why it is slow.

python

def sum_recursive(items):
    if not items:            # base case: T(0) = O(1)
        return 0
    return items[0] + sum_recursive(items[1:])   # T(n) = T(n-1) + O(1) -> O(n) calls

What we're doing: Confirm a T(n) = T(n-1) + O(1) recursive function gives the same result as its O(n)-call iterative equivalent.

analyzing_recursion.pypython

def sum_recursive(items):
    if not items:
        return 0
    return items[0] + sum_recursive(items[1:])


def sum_iterative(items):
    total = 0
    for x in items:
        total += x
    return total


print(sum_recursive([1, 2, 3, 4]), sum_iterative([1, 2, 3, 4]))

1: Each call does O(1) work (one addition) and recurses once on a list one element shorter — T(n) = T(n-1) + O(1), which unrolls to exactly n calls before the empty-list base case.
2: The base case, T(0), does O(1) work and makes no further recursive call — this is where the recurrence stops.

Output

10 10

Why this works: Both functions agree (10), confirming the recursive version is correct — and its recurrence, T(n) = T(n-1) + O(1), is the same shape as the loop counting to n once, which is exactly why both are O(n).

Remember: Write the recurrence — what one call costs on its own, plus what it recurses into — and the growth class usually falls out without needing exact math.

Amortized complexity

standardintermediate

Amortized complexity averages an operation's cost over a long sequence of calls, not any single call. list.append() is O(1) amortized even though it occasionally pays O(n) to grow into a bigger block of memory.

Think of it as

Python's list over-allocates when it grows: appending sometimes triggers a full copy into a larger buffer (expensive, O(n)), but that new buffer has room for many more cheap appends (O(1) each) before it fills up again. Spread the occasional expensive copy across all the cheap appends that earned it, and the AVERAGE cost per append stays O(1) — that average is what 'amortized' means.

python

items = []
for i in range(1000):
    items.append(i)   # O(1) amortized: most appends are O(1); rare resizes are O(n), spread thin

Remember: Amortized O(1) means the occasional expensive operation is rare enough that the AVERAGE over a long sequence still comes out to O(1) — not that every single call is cheap.

Common complexity classes, in order

corebeginner

From fastest-growing-slowest to slowest-growing-fastest: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), O(n!). Each is dramatically worse than the one before it as n grows.

Think of it as

Picture n=20. A constant-time operation does 1 unit of work no matter what. Linear does 20. Quadratic does 400. Exponential does over a million. Factorial does over two quintillion — already far beyond anything a computer can finish, at an input size small enough to fit on one hand. The classes are not evenly spaced; each one is a different kind of explosion.

What we're doing: Measure the real comparison count for O(n) and O(n²) work at three input sizes and confirm the growth matches the class.

complexity_classes.pypython

def constant_time(items):
    return items[0] if items else None


def linear_time(items, target):
    comparisons = 0
    for x in items:
        comparisons += 1
        if x == target:
            return comparisons
    return comparisons


def quadratic_time(items):
    comparisons = 0
    for i in items:
        for j in items:
            comparisons += 1
    return comparisons


for n in (5, 10, 20):
    items = list(range(n))
    print(n, linear_time(items, -1), quadratic_time(items))

1: Indexing does the same one unit of work regardless of n — the defining trait of O(1).
8: target=-1 never matches, so this always runs to completion — the comparison count equals n exactly.
15: Doubling n from 10 to 20 quadruples this count (100 -> 400) — exactly n^2's signature, distinct from linear_time's count merely doubling.

Output

5 5 25
10 10 100
20 20 400

Why this works: linear_time's count always equals n exactly (5, 10, 20) — doubling n doubles the work. quadratic_time's count is n^2 (25, 100, 400) — doubling n from 10 to 20 quadruples the work, the real, measured signature of O(n^2) rather than an assumed one.

Assuming a nested loop is always O(n²)

Wrong

python

# "there's a loop inside a loop, so this is O(n^2)" — not always true
def has_close_pair(sorted_items, max_gap):
    for i, x in enumerate(sorted_items):
        for y in sorted_items[i + 1:i + 4]:   # inner loop only ever runs up to 3 times
            if y - x <= max_gap:
                return True
    return False

Better

python

# the inner loop's bound is a CONSTANT (3), not n — this is O(n), not O(n^2)
def has_close_pair(sorted_items, max_gap):
    for i, x in enumerate(sorted_items):
        for y in sorted_items[i + 1:i + 4]:
            if y - x <= max_gap:
                return True
    return False

What you see: Nothing crashes — the mistake is purely in the complexity CLAIM: calling this O(n^2) from the shape of the code alone, without checking what the inner loop actually iterates over.

Why: Multiplying to O(n^2) is only correct when the inner loop's own bound scales with n. Here the inner slice is always at most 3 elements, a constant — so the true cost is O(n) * O(1) = O(n). Reading the code's SHAPE (loop-in-a-loop) is not the same as analyzing what each loop actually bounds.

All seven classes, one picture — note the log scale

Y-axis is log-scaled — without it, every class except O(n!) would be an invisible flat line at the bottom. n=1 is excluded because log2(1)=0, which a log scale cannot plot. Every value computed with math.log2/math.factorial, same as the table above.

The seven classes, fastest to slowest, with real operation counts at n = 20

The seven classes, fastest to slowest, with real operation counts at n = 20
Class	Name	Ops at n = 20	Typical example
O(1)	Constant	1	dict/set lookup, array index by position
O(log n)	Logarithmic	~4.3	binary search
O(n)	Linear	20	a single loop over the input
O(n log n)	Linearithmic	~86.4	comparison-based sorting (Timsort, merge sort)
O(n²)	Quadratic	400	a loop nested inside a loop
O(2ⁿ)	Exponential	1,048,576	trying every subset of n items
O(n!)	Factorial	2,432,902,008,176,640,000	trying every ordering (permutation) of n items

Together

python

import math

n = 20
print("O(1):        1")
print("O(log n):   ", round(math.log2(n), 1))
print("O(n):       ", n)
print("O(n log n): ", round(n * math.log2(n), 1))
print("O(n^2):     ", n ** 2)
print("O(2^n):     ", 2 ** n)
print("O(n!):      ", math.factorial(n))

Remember: Memorize the order — O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), O(n!) — and always check what an inner loop actually bounds before assuming "nested loop" means O(n²).

Reading constraints to guess required complexity

standardbeginner

A rough rule of thumb: a typical time limit allows about 10^8 simple operations. Divide that by the complexity formula at the stated n, and if the result is comfortably above 1, that complexity is safe to attempt.

Think of it as

This turns 'is O(n^2) fast enough?' from a guess into arithmetic: compute n^2 at the stated n, compare it to the ~10^8-operations-per-second budget. n=10^5 gives n^2 = 10^10 — a hundred times over budget, so O(n^2) is ruled out and something like O(n log n) is expected instead.

python

OPS_PER_SECOND = 10**8

def fits_time_limit(n, complexity_ops):
    return complexity_ops(n) <= OPS_PER_SECOND

What we're doing: Check whether an O(n^2) and an O(n) approach both fit a ~10^8-operation budget at n = 10^5.

reading_constraints.pypython

OPS_PER_SECOND = 10**8


def fits_time_limit(n, complexity_ops):
    return complexity_ops(n) <= OPS_PER_SECOND


print(fits_time_limit(10**5, lambda n: n * n))
print(fits_time_limit(10**5, lambda n: n))

1: A rough, widely-used rule of thumb — real limits vary by language and judge, but this is close enough to rule approaches in or out quickly.
7: (10^5)^2 = 10^10, ten times the 10^8 budget — this line evaluates to False, confirming O(n^2) is ruled out at this n before writing any real code.

Output

False
True

Why this works: n^2 at n=10^5 is 10^10 — over budget, hence False. n itself is just 10^5 — far under budget, hence True. This is exactly how a stated constraint (n ≤ 10^5) turns into a decision (need something at or below roughly O(n log n)) before any code is written.

Remember: Roughly 10^8 simple operations fit a typical time limit — compute the complexity formula at the stated n and compare, instead of guessing whether an approach is "probably fine".

Space complexity of recursion (call stack depth)

standardintermediate

Every recursive call that has not yet returned stays on the call stack, using memory. A recursion that goes n calls deep before its base case uses O(n) space, even if an equivalent loop would use O(1).

Think of it as

Each pending recursive call is a stack frame — a small block of memory holding that call's local variables and where to resume. A loop reuses the same frame every iteration (O(1) space); recursion that goes n levels deep before returning keeps n frames alive simultaneously, which is real, measurable memory the loop version never pays.

python

def sum_recursive(items):        # O(n) space: n pending calls at the deepest point
    if not items:
        return 0
    return items[0] + sum_recursive(items[1:])

def sum_iterative(items):        # O(1) space: one frame, reused every iteration
    total = 0
    for x in items:
        total += x
    return total

What we're doing: Confirm a recursive and an iterative sum agree on the result, despite very different space costs.

space_of_recursion.pypython

def sum_recursive(items):
    if not items:
        return 0
    return items[0] + sum_recursive(items[1:])


def sum_iterative(items):
    total = 0
    for x in items:
        total += x
    return total


print(sum_recursive([1, 2, 3, 4]), sum_iterative([1, 2, 3, 4]))

1: At the deepest point, 4 calls are all still pending (none has returned yet) — that is O(n) space for a 4-element list.
7: total is one variable, reused every iteration — no growing set of pending calls, so this is O(1) space regardless of list length.

Output

10 10

Why this works: Both return the same correct answer, so space is the only real difference between them — sum_recursive briefly needs memory proportional to the list length just to hold its pending calls, while sum_iterative never does.

Remember: Recursion depth is memory, not just time — n pending calls means O(n) space, even for a problem an O(1)-space loop could solve.

Python-specific complexity facts

The concrete operation costs that decide which data structure and idiom to reach for.

list index/append/pop-from-end: O(1)

referencebeginner

Reading items[i], adding with items.append(x), and removing the last item with items.pop() are all O(1) — none of them need to touch any other element.

python

items = [10, 20, 30]
items.append(40)   # O(1)
items[1]            # O(1)
items.pop()         # O(1) — removes and returns the LAST item

Remember: Index access, append, and pop-from-the-end are the three O(1) list operations — everything else that touches position 0 or the middle is not.

list insert/pop/delete at an arbitrary index: O(n)

referencebeginner

Inserting or removing anywhere except the end forces every following element to shift by one position — items.insert(0, x) and items.pop(0) are both O(n), not O(1).

python

items = [10, 20, 30]
items.insert(0, 5)   # O(n) — 10, 20, 30 all shift right by one
items.pop(0)         # O(n) — every remaining item shifts left by one
del items[1]         # O(n) — same shifting cost

What we're doing: Confirm inserting at the front leaves the list in the shifted order the O(n) cost implies.

list_slow_ops.pypython

items = [10, 20, 30]
items.insert(0, 5)
print(items)

2: Every one of the three existing elements had to move one position to the right to make room at index 0 — that shifting is the O(n) cost, not the insertion itself.

Output

[5, 10, 20, 30]

Why this works: The result confirms 5 is now first and everything else shifted right by exactly one position — that shift is real work proportional to how many elements came after the insertion point, which is what makes this O(n) rather than O(1).

Remember: Anything that is not at the very end (insert, pop, del at an index) costs O(n) on a list, because everything after it has to shift.

Membership check (`in`): list O(n) vs dict/set O(1) average

corebeginner

x in some_list scans from the start until it finds x or reaches the end — O(n). x in some_set or x in some_dict uses hashing to jump straight to where x would be — O(1) on average. Same syntax, very different cost.

Think of it as

A list has no index by VALUE, only by position — checking membership means looking at items one at a time until a match turns up or they run out, which is exactly linear search. A set or dict computes a hash of x and jumps almost directly to the right bucket, so membership does not get slower as more items are added — that is the entire reason 'the single most common optimization trick' (trading space for a set/dict) exists.

What we're doing: Manually count the comparisons a linear membership check performs, and confirm a set finds the same answer without that scan.

membership_check.pypython

def linear_scan_comparisons(container, target):
    comparisons = 0
    for x in container:
        comparisons += 1
        if x == target:
            return comparisons
    return comparisons


big_list = list(range(10_000))
print(linear_scan_comparisons(big_list, 9_999), 9_999 in set(big_list))

1: This manually reimplements what `in` does on a list internally — one comparison per element until a match is found.
10: Finding the LAST element in a 10,000-item list costs 10,000 comparisons via linear scan — the worst case for `in` on a list — while the same check against a set does not scan at all.

Output

10000 True

Why this works: 10,000 comparisons is exactly the worst case for a linear scan over a 10,000-element container — the element being searched for was last. A set finds the same True without walking every element first, which is the entire practical difference between O(n) and O(1) membership checks at scale.

Checking membership against a list inside a loop

Wrong

python

def find_new_items(candidates, existing_list):
    return [c for c in candidates if c not in existing_list]   # O(n) check, n times -> O(n^2)

Better

python

def find_new_items(candidates, existing_items):
    existing_set = set(existing_items)                          # O(n) once
    return [c for c in candidates if c not in existing_set]     # O(1) check, n times -> O(n)

What you see: Both versions return the same correct list — the "wrong" version is not incorrect, it is quadratic where a linear solution was available, and the gap grows with input size.

Why: `c not in existing_list` re-scans the entire list from scratch for every one of the `candidates` — n candidates times an O(n) scan each is O(n^2). Converting `existing_items` to a set costs O(n) exactly once, after which every membership check drops to O(1) average — the classic space-for-time trade this whole roadmap keeps coming back to.

Contains DuplicateeasyLeetCode
A set turns "have I seen this value before?" into an O(1) check per element instead of an O(n) scan of everything seen so far.
Two SumeasyLeetCode
Walk the array once, checking "is target - x already in a set/dict I have seen?" before adding x to it — the canonical use of O(1) membership to avoid the O(n^2) brute force.

Remember: `in` on a list is O(n); `in` on a set or dict is O(1) average — if you check membership more than once, convert to a set first.

dict/set average-case get/insert/delete: O(1)

referencebeginner

Getting, inserting, or deleting a key in a dict, or an item in a set, is O(1) on average — hashing computes roughly where it lives directly, instead of searching for it.

python

cache = {}
cache["user:42"] = {"name": "Ada"}   # O(1) average insert
cache["user:42"]                       # O(1) average get
del cache["user:42"]                   # O(1) average delete

Two SumeasyLeetCode
Every lookup against the running dict of "numbers seen so far" is O(1) average — that is the entire reason the hash-map solution beats the O(n^2) brute force.
Contains DuplicateeasyLeetCode
Insert into a set and check membership as you go — both O(1) average operations, done n times.

Remember: dict/set get, insert, and delete are all O(1) on average — the same operations on a list are O(n) unless they touch only the very end.

String concatenation in a loop is O(n²)

corebeginner

Building a string with result += piece inside a loop is O(n^2) overall, because strings are immutable — each += copies the ENTIRE string so far into a new, longer one. ''.join(pieces) builds the result once, in O(n).

Think of it as

Because a Python string cannot be changed in place, result += piece does not extend result — it builds an entirely new string containing everything result already had, plus piece, and copies all of it. The first += copies 1 character's worth, the second copies 2, and so on — by the n-th piece, you have copied roughly 1+2+...+n characters in total, which is O(n^2). ''.join() knows the final size in advance and writes each piece into it exactly once — O(n) total.

What we're doing: Compute the real total number of characters copied by a += loop over n pieces, and confirm it grows quadratically.

string_concat.pypython

def total_chars_copied(n):
    return sum(range(1, n + 1))


for n in (10, 100, 1000):
    print(n, total_chars_copied(n))

1: The i-th += copies i characters' worth of the string-so-far — summing 1 through n gives the real total work done across the whole loop.
2: sum(1..n) = n(n+1)/2, which grows with n^2 — confirmed by the measured totals: growing n by 10x grows the total by roughly 100x.

Output

10 55
100 5050
1000 500500

Why this works: n=10 -> 55 characters copied; n=100 -> 5,050 (about 92x more, for 10x more pieces); n=1000 -> 500,500 (about 99x more again) — the ratio approaching 100x for every 10x increase in n is the real, measured signature of O(n^2), not an assumption.

Building a large string with += in a loop instead of ''.join()

Wrong

python

def build_with_plus_equals(words):
    result = ""
    for w in words:
        result += w
    return result

Better

python

def build_with_join(words):
    return "".join(words)

What you see: Both return the identical string for small inputs, so the bug is invisible in a quick test — it only shows up as the input grows, when the += version becomes measurably, and then dramatically, slower than join().

Why: build_with_plus_equals pays the O(n^2) copying cost described above; build_with_join computes the final length once and writes each word into it exactly one time, for O(n) total. Both are correct — one just gets catastrophically slower as `words` grows, which the copy-count math above predicts exactly.

The copy count curves upward — that bend is O(n²)

Every point is sum(range(1, n + 1)), same formula as the table below — a straight-line (O(n)) cost would be a straight line here; this visibly bends upward, which is what O(n²) looks like.

Measured total characters copied by result += piece, across n pieces

Measured total characters copied by result += piece, across n pieces
Pieces (n)	Total characters copied (1+2+...+n)
10	55
100	5,050
1,000	500,500

Together

python

def total_chars_copied(n):
    return sum(range(1, n + 1))

for n in (10, 100, 1000):
    print(n, total_chars_copied(n))
# 10 55 / 100 5050 / 1000 500500

Add StringseasyLeetCode
Build the digit-by-digit result into a list and reverse/join it at the end, rather than += a growing string inside the loop.
Reverse Words in a StringmediumLeetCode
The idiomatic solution collects words in a list and " ".join()s them once — exactly the fix this concept teaches, not accumulated with +=.

Remember: Never build a string with += inside a loop — the immutability of strings makes it O(n^2). Collect the pieces in a list and call ''.join() once.

Slicing a list/string is O(k), not O(1)

standardbeginner

items[a:b] copies k = b - a elements into a brand-new list (or string) — it is O(k), never O(1), no matter how large the original container is.

Think of it as

A slice is not a view into the original — it is a fresh copy. Copying k elements takes time proportional to k, so a slice of length 3 is cheap regardless of the source's size, while items[:] on a million-element list copies all million, an easy hidden cost inside what LOOKS like a constant-time expression.

What we're doing: Confirm a slice produces a genuinely new list of exactly the requested length.

slicing_cost.pypython

a = list(range(10))
b = a[2:5]
print(b, len(b))

2: b is a new list, built by copying exactly 3 elements (indices 2, 3, 4) out of a — the cost is proportional to that 3, not to len(a).

Output

[2, 3, 4] 3

Why this works: b is a distinct object holding a copy of 3 elements — that copy is the O(k) cost slicing always pays, whether a has 10 elements or 10 million.

Reverse StringeasyLeetCode
The required in-place solution deliberately avoids s[::-1] (an O(n) copy) in favor of two-pointer swaps — a direct illustration of when a slice's O(k) cost is worth avoiding.
Rotate ArraymediumLeetCode
The one-line slice solution nums[:] = nums[-k:] + nums[:-k] is easy to write but costs two O(k)/O(n-k) copies — compare it against the O(1)-space reversal trick.

Remember: A slice always copies k elements — O(k), not O(1) — so a slice inside a loop (especially a full items[:] or items[i:]) is a real, easy-to-miss cost, not free.

sorted() / list.sort(): O(n log n), Timsort

referencebeginner

Both sorted() (returns a new list) and list.sort() (sorts in place) run in O(n log n) worst case, using Timsort — a hybrid of merge sort and insertion sort tuned for real-world, partially-ordered data.

python

sorted([3, 1, 2])          # [1, 2, 3] — new list, O(n log n)
items = [3, 1, 2]
items.sort()                # in place, O(n log n), returns None
sorted(items, key=len)      # sort by a derived value instead of the items themselves

Contains DuplicateeasyLeetCode
sorted(nums) first, then a single pass checking adjacent equal elements — the sort-based alternative to the hash-set approach.
Merge IntervalsmediumLeetCode
sorted(intervals) by start time is the very first line of the idiomatic solution — nothing else about the merge works until the input is ordered.

Remember: sorted()/list.sort() are both O(n log n) worst case, using Timsort — reach for them instead of writing a manual sort in almost every practical case.