Complexity analysis

coreCommon atGoogleMetaAmazonAnthropicStripePractise in the Sandbox →

Complexity analysis asks one question: when the input gets bigger, how much more work and memory does this code need? You answer it by counting how often the innermost step runs, then keeping only the fastest-growing term: O(n), O(n log n), O(n²). Read it in both directions: analyse code you wrote, and read the input limits (n ≤ 10⁵) to work out which complexity the interviewer expects.

The idea in plain words

Imagine you have to find a friend’s name in a stack of 1,000 unsorted business cards. You flip through them one by one. In the worst case that’s 1,000 looks. With 2,000 cards it’s 2,000 looks. Work grows in step with the input: that’s linear, written O(n).

Now the cards are sorted alphabetically. You open the stack in the middle, see whether the name is before or after, and throw away half. 1,000 cards take about 10 halvings. 2,000 take 11. Doubling the input added one step: that’s logarithmic, O(log n).

Big-O ignores two things on purpose:

Constant factors. 3n and 100n are both O(n). Machines, languages and compilers change constants; they don’t change the shape of the curve.
Smaller terms. n² + 50n + 7 is O(n²). For n = 10⁵ the n² part is 10¹⁰ and the 50n part is 5·10⁶, a rounding error.

What’s left is the growth rate. It tells you what happens at 10× the data, which is what an interviewer means by “will this scale?”.

See it

Pick a loop shape and a size. Every time the highlighted line runs, a cell fills in. The filled area is the running time. Compare “nested loops” (a full square) with “j starts after i” (half the square, still O(n²)) and “loop × doubling loop” (a thin log-shaped stripe per row).

Count the operations

step through

loop shapen = 8

for i in 0..n-1:
    for j in i+1..n-1:
        work(i, j)

rows: i · columns: j

ops0

Each time the highlighted line runs, one cell fills in. Count the cells and you have the running time.

1 / 30speed

running nowalready rannever runs

Doubling test. ops(8) = 28, ops(16) = 120, ops(32) = 496. Each doubling multiplies the work by about 4.29 then 4.13. A ratio near 1 means log, 2 means linear, a bit over 2 means n log n, 4 means quadratic.

The doubling test under the grid is the experimental version of the same idea, from Sedgewick and Wayne: run with n, then 2n. If the time roughly doubles, you’re linear. If it quadruples, quadratic. You can do this in your head during an interview: “if I double the list, how much more does this loop do?”

Then see how the curves pull apart. Drag n and toggle classes on and off:

How fast does work grow?

drag n

n = 16

O(log n): 4 opsO(n): 16 opsO(n log n): 64 opsO(n²): 256 ops

When to reach for it

Always. But there are moments in an interview where it is the whole point:

You hear or see…	What it’s asking
“n ≤ 10⁵” (or any explicit limit)	Back out the target complexity before choosing an approach. See the table below.
“Can you do better?”	Your current bound has a known improvement; name the bottleneck step first.
“What’s the complexity?” after you code	Time and space, with every input size named (n, m, k), plus the reason.
“What if it’s called a million times?”	Per-call cost now matters more than one-off setup: think precomputation, amortized cost.
“What if the data doesn’t fit in memory?”	Space complexity and access pattern (streaming, one pass) become the constraint.

Read the constraints backwards

A typical judge or interviewer budget is about one second, which is roughly 10⁸ simple operations in compiled or JIT languages (C#, TypeScript on V8) and closer to 10⁷ in CPython. From that you get a rule of thumb that holds up remarkably well:

If n is up to…	Aim for	Typical technique
10–12	O(n!)	try every ordering (permutations)
20–25	O(2ⁿ) or O(2ⁿ·n)	every subset, bitmask DP
100–500	O(n³)	triple loop, interval DP, Floyd-Warshall
1,000–5,000	O(n²)	all pairs, 2-D DP
10⁵–10⁶	O(n log n)	sort, heap, binary search, balanced tree
10⁷–10⁸	O(n)	one pass, hash map, two pointers
beyond	O(log n) or O(1)	math, binary search on the answer

Drag n and switch the language speed to see the same table as an instrument:

What fits in about one second?

drag n

n = 100,000language speed

classoperations (log scale, dashed line = 1 s budget)ops≈ timeO(log n)

17< 1 msO(√n)

316< 1 msO(n)

100k1.0 msO(n log n)

2M17 msO(n²)

1.0·10¹⁰1.7 minO(n³)

1.0·10¹⁵116 daysO(2ⁿ)

> 10³⁰> 1000 yearsO(n!)

> 10³⁰> 1000 years

comfortabletight: constants mattertoo slow

With n = 100k, the slowest class that still fits is O(n log n). If the problem says n ≤ 100k, the interviewer is quietly telling you to aim for about that.

How it works

Analysing code: the recipe

Name every input size. n items, m queries, k distinct keys, L characters per string. Don’t collapse them into one n.
Find the repeated work. For each loop, ask how far its variable travels in total. For recursion, ask how many calls happen and what each one costs.
Combine. Loops one after another add (n + m). Loops inside each other multiply (n · m). A loop that halves its range contributes a log factor.
Charge library calls honestly. x in list, slice, sort, indexOf, string concatenation: each has its own cost, and inside a loop it multiplies.
Simplify. Drop constant factors and lower-order terms, but keep independent variables: O(n + m) stays O(n + m).

The snippet below counts the operations of three common shapes and checks the counts against their formulas. Notice that the triangular loop does exactly n(n−1)/2 steps: half of n², and still O(n²).

import math


def triangle(n: int) -> int:
    """Count inner-loop steps when j starts after i: every unordered pair once."""
    ops = 0
    for i in range(n):
        for j in range(i + 1, n):  # 1. inner length shrinks: n-1, n-2, ..., 0
            ops += 1
    return ops                     # 2. sum = n(n-1)/2, still O(n^2)


def halving(n: int) -> int:
    """Count steps of a loop that halves its remaining work each time."""
    ops = 0
    while n >= 1:                  # 3. n, n/2, n/4, ... reaches 0 after ~log2(n) steps
        ops += 1
        n //= 2
    return ops


def n_log_n(n: int) -> int:
    """An O(n) outer loop around an O(log n) doubling loop."""
    ops = 0
    for _ in range(n):
        j = 1
        while j < n:               # 4. j = 1, 2, 4, ... < n: ceil(log2 n) steps
            ops += 1
            j *= 2
    return ops


if __name__ == "__main__":
    assert triangle(10) == 45                       # 10*9/2
    assert halving(1_000_000) == 20                 # floor(log2 1e6) + 1
    assert halving(1) == 1 and halving(0) == 0
    assert n_log_n(1024) == 1024 * 10               # exactly n * log2 n for powers of 2
    assert n_log_n(1000) == 1000 * math.ceil(math.log2(1000))
    print("ok")

import assert from "node:assert/strict";

/** Count inner-loop steps when j starts after i: every unordered pair once. */
export function triangle(n: number): number {
  let ops = 0;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) ops++; // 1. inner length shrinks: n-1, n-2, ..., 0
  }
  return ops; // 2. sum = n(n-1)/2, still O(n^2)
}

/** Count steps of a loop that halves its remaining work each time. */
export function halving(n: number): number {
  let ops = 0;
  for (let m = n; m >= 1; m = Math.floor(m / 2)) ops++; // 3. ~log2(n) steps
  return ops;
}

/** An O(n) outer loop around an O(log n) doubling loop. */
export function nLogN(n: number): number {
  let ops = 0;
  for (let i = 0; i < n; i++) {
    for (let j = 1; j < n; j *= 2) ops++; // 4. j = 1, 2, 4, ... < n: ceil(log2 n) steps
  }
  return ops;
}

assert.equal(triangle(10), 45); // 10*9/2
assert.equal(halving(1_000_000), 20); // floor(log2 1e6) + 1
assert.equal(halving(1), 1);
assert.equal(halving(0), 0);
assert.equal(nLogN(1024), 1024 * 10); // exactly n * log2 n for powers of 2
assert.equal(nLogN(1000), 1000 * Math.ceil(Math.log2(1000)));
console.log("ok");

// Count inner-loop steps when j starts after i: every unordered pair once.
static long Triangle(int n)
{
    long ops = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) ops++; // 1. inner length shrinks: n-1, n-2, ..., 0
    return ops;                                 // 2. sum = n(n-1)/2, still O(n^2)
}

// Count steps of a loop that halves its remaining work each time.
static int Halving(int n)
{
    int ops = 0;
    for (int m = n; m >= 1; m /= 2) ops++; // 3. n, n/2, n/4, ...: ~log2(n) steps
    return ops;
}

// An O(n) outer loop around an O(log n) doubling loop.
static long NLogN(int n)
{
    long ops = 0;
    for (int i = 0; i < n; i++)
        for (long j = 1; j < n; j *= 2) ops++; // 4. j = 1, 2, 4, ... < n: ceil(log2 n) steps
    return ops;
}

if (Triangle(10) != 45) throw new Exception("expected 45");
if (Halving(1_000_000) != 20) throw new Exception("expected 20");
if (Halving(1) != 1 || Halving(0) != 0) throw new Exception("edge cases");
if (NLogN(1024) != 1024 * 10) throw new Exception("expected n log n");
if (NLogN(1000) != 1000 * (long)Math.Ceiling(Math.Log2(1000))) throw new Exception("expected 10000");
Console.WriteLine("ok");

Amortized analysis: the average over a sequence

Some operations are usually cheap but occasionally expensive. A growable array (Python list, JS Array, C# List<T>) has spare slots. When it runs out, it allocates a bigger block and copies every element. That one push costs O(n).

Amortized cost asks: over any sequence of n operations, what is the total, divided by n? Push into the sandbox and watch the running average (the line):

Amortized cost of a growing array

sandbox

growth rule

memory: 9 used of 16 slots

cost 1 (free slot)resize: 1 + copiesrunning average

pushes9

capacity16

total work24

worst push9

average / push2.67

The array was full at 8 items, so this push allocated 16 slots and copied all 8 items first. Expensive, but rare.

With doubling, the copies are 1 + 2 + 4 + … + n/2 < n in total, so n pushes cost less than 3n work: O(1) amortized per push. With a fixed +4 growth, the copies add up to about n²/8 and the average climbs forever. Real runtimes grow geometrically for exactly this reason: C# List<T> doubles, V8 grows arrays by about 1.5×, and CPython over-allocates lists by about 1.125×. Any constant factor above 1 gives O(1) amortized.

Pick a sequence of n operations (the worst one you can think of).
Add up the total cost. Often you charge each element for the moves it can ever make: an element is copied at most a constant number of times “on average”, or pushed and popped at most once.
Divide by n. That is the amortized cost per operation, and it’s a guarantee for the whole sequence, not a hope.

class DynArray:
    """A growable array that doubles its capacity, counting element copies."""

    def __init__(self) -> None:
        self.cap = 1
        self.size = 0
        self.slots: list[int | None] = [None]
        self.copies = 0                      # total work spent on resizing

    def push(self, x: int) -> None:
        if self.size == self.cap:            # 1. full: allocate 2x and copy everything
            bigger: list[int | None] = [None] * (self.cap * 2)
            for i in range(self.size):
                bigger[i] = self.slots[i]
                self.copies += 1
            self.slots, self.cap = bigger, self.cap * 2
        self.slots[self.size] = x            # 2. the normal O(1) write
        self.size += 1


if __name__ == "__main__":
    a = DynArray()
    n = 1_000
    for k in range(n):
        a.push(k)
    # 3. copies = 1 + 2 + 4 + ... + 512 = 1023 < 2n, so each push is O(1) amortized
    assert a.copies == 1023 and a.copies < 2 * n
    assert a.cap == 1024 and a.size == n
    print("ok")

import assert from "node:assert/strict";

/** A growable array that doubles its capacity, counting element copies. */
export class DynArray {
  cap = 1;
  size = 0;
  slots: (number | undefined)[] = [undefined];
  copies = 0; // total work spent on resizing

  push(x: number): void {
    if (this.size === this.cap) {
      // 1. full: allocate 2x and copy everything
      const bigger: (number | undefined)[] = new Array(this.cap * 2).fill(undefined);
      for (let i = 0; i < this.size; i++) {
        bigger[i] = this.slots[i];
        this.copies++;
      }
      this.slots = bigger;
      this.cap *= 2;
    }
    this.slots[this.size++] = x; // 2. the normal O(1) write
  }
}

const a = new DynArray();
const n = 1_000;
for (let k = 0; k < n; k++) a.push(k);
// 3. copies = 1 + 2 + 4 + ... + 512 = 1023 < 2n, so each push is O(1) amortized
assert.equal(a.copies, 1023);
assert.ok(a.copies < 2 * n);
assert.equal(a.cap, 1024);
console.log("ok");

var a = new DynArray();
const int n = 1_000;
for (int k = 0; k < n; k++) a.Push(k);
// 3. copies = 1 + 2 + 4 + ... + 512 = 1023 < 2n, so each push is O(1) amortized
if (a.Copies != 1023 || a.Copies >= 2 * n) throw new Exception($"copies {a.Copies}");
if (a.Capacity != 1024 || a.Size != n) throw new Exception("capacity");
Console.WriteLine("ok");

// A growable array that doubles its capacity, counting element copies.
class DynArray
{
    private int[] _slots = new int[1];
    public int Size { get; private set; }
    public int Capacity => _slots.Length;
    public long Copies { get; private set; } // total work spent on resizing

    public void Push(int x)
    {
        if (Size == _slots.Length)            // 1. full: allocate 2x and copy everything
        {
            var bigger = new int[_slots.Length * 2];
            for (int i = 0; i < Size; i++) { bigger[i] = _slots[i]; Copies++; }
            _slots = bigger;
        }
        _slots[Size++] = x;                   // 2. the normal O(1) write
    }
}

The same argument explains why a sliding window’s inner while loop is still O(n) overall: the left pointer can move at most n times in total. See sliding window and monotonic stack.

Best, average, worst, expected, amortized

These words get mixed up. They answer different questions:

Term	Averaged over…	Example
Worst case	nothing: the nastiest input of size n	Quicksort with a first-element pivot on sorted input: O(n²)
Best case	nothing: the kindest input	Insertion sort on sorted input: O(n). Rarely useful to quote.
Average case	a distribution of inputs	Quicksort on random input: O(n log n)
Expected	the algorithm’s own random choices, for any input	Quicksort with a random pivot: O(n log n) expected on every input
Amortized	a sequence of operations, worst case	Dynamic array push: O(1) amortized; a single push can be O(n)

Hash maps are O(1) expected (or average) per operation and O(n) worst case if many keys collide. Say “O(1) on average” when you use one; it’s the precise claim.

Space complexity

Space counts memory that grows with the input, on top of the input itself (auxiliary space):

New arrays, maps, sets, strings you build. A seen set over n items is O(n).
The recursion stack. Each pending call is a frame. Recursing n levels deep is O(n) space even if you allocate nothing. See recursion.
Copies you didn’t notice. Slicing xs[1:] in Python or xs.slice(1) in JS allocates a new array every call.

By convention the output isn’t counted (returning n results needs O(n) whatever you do), but say so explicitly if it’s large.

Optimizing: the playbook

Faster code almost always comes from removing repeated work. Find the step that runs most often, and ask which structure or precomputation makes it cheaper. The classic “are all values distinct?” problem shows three levels:

def distinct_brute(xs: list[int]) -> bool:
    """Compare every pair. O(n^2) time, O(1) extra space."""
    for i in range(len(xs)):
        for j in range(i + 1, len(xs)):
            if xs[i] == xs[j]:
                return False
    return True


def distinct_sorted(xs: list[int]) -> bool:
    """Sort a copy so equal values sit next to each other. O(n log n) time, O(n) space."""
    s = sorted(xs)
    return all(s[i] != s[i + 1] for i in range(len(s) - 1))


def distinct_set(xs: list[int]) -> bool:
    """Remember what you've seen. O(n) expected time, O(n) space."""
    seen: set[int] = set()
    for x in xs:
        if x in seen:  # average O(1) hash lookup replaces the inner loop
            return False
        seen.add(x)
    return True


if __name__ == "__main__":
    for f in (distinct_brute, distinct_sorted, distinct_set):
        assert f([3, 1, 4, 1, 5]) is False
        assert f([2, 7, 1, 8]) is True
        assert f([]) is True
    print("ok")

import assert from "node:assert/strict";

/** Compare every pair. O(n^2) time, O(1) extra space. */
export function distinctBrute(xs: number[]): boolean {
  for (let i = 0; i < xs.length; i++)
    for (let j = i + 1; j < xs.length; j++) if (xs[i] === xs[j]) return false;
  return true;
}

/** Sort a copy so equal values sit next to each other. O(n log n) time, O(n) space. */
export function distinctSorted(xs: number[]): boolean {
  const s = [...xs].sort((a, b) => a - b); // numeric comparator: default sort is by string
  for (let i = 0; i + 1 < s.length; i++) if (s[i] === s[i + 1]) return false;
  return true;
}

/** Remember what you've seen. O(n) expected time, O(n) space. */
export function distinctSet(xs: number[]): boolean {
  const seen = new Set<number>();
  for (const x of xs) {
    if (seen.has(x)) return false; // average O(1) hash lookup replaces the inner loop
    seen.add(x);
  }
  return true;
}

for (const f of [distinctBrute, distinctSorted, distinctSet]) {
  assert.equal(f([3, 1, 4, 1, 5]), false);
  assert.equal(f([2, 7, 1, 8]), true);
  assert.equal(f([]), true);
}
console.log("ok");

// Compare every pair. O(n^2) time, O(1) extra space.
static bool DistinctBrute(int[] xs)
{
    for (int i = 0; i < xs.Length; i++)
        for (int j = i + 1; j < xs.Length; j++)
            if (xs[i] == xs[j]) return false;
    return true;
}

// Sort a copy so equal values sit next to each other. O(n log n) time, O(n) space.
static bool DistinctSorted(int[] xs)
{
    var s = (int[])xs.Clone();
    Array.Sort(s);
    for (int i = 0; i + 1 < s.Length; i++)
        if (s[i] == s[i + 1]) return false;
    return true;
}

// Remember what you've seen. O(n) expected time, O(n) space.
static bool DistinctSet(int[] xs)
{
    var seen = new HashSet<int>();
    foreach (var x in xs)
        if (!seen.Add(x)) return false; // Add returns false if x was already there
    return true;
}

foreach (var f in new Func<int[], bool>[] { DistinctBrute, DistinctSorted, DistinctSet })
{
    if (f([3, 1, 4, 1, 5])) throw new Exception("expected duplicate");
    if (!f([2, 7, 1, 8])) throw new Exception("expected distinct");
    if (!f([])) throw new Exception("empty is distinct");
}
Console.WriteLine("ok");

Bottleneck	Trade	Becomes
“for each item, scan all items”	a hash set or map of what you’ve seen	O(n²) → O(n) expected, O(n) space
repeated range sums	prefix sums, built once	O(n) per query → O(1)
“find the closest / k-th / boundary” in a scan	sort once, then binary search or two pointers	O(n²) → O(n log n)
repeatedly take the min/max of a changing set	a heap	O(n) per take → O(log n)
the same subproblem solved many times	memoization / DP	exponential → polynomial
“every contiguous range”	a sliding window	O(n²) → O(n)

Most of these trade space for time. Say the trade out loud: “I’ll spend O(n) extra memory to get O(n) time.”

What it costs

Analysis is free; library calls are not. These are the costs to have at your fingertips (average case for hash structures):

Operation	Python	TypeScript / JS	C#
index read/write	`xs[i]` O(1)	`xs[i]` O(1)	`xs[i]` O(1)
append at end	`append` O(1) amortized	`push` O(1) amortized	`List.Add` O(1) amortized
insert/remove at front	`insert(0, x)`, `pop(0)` O(n); use `collections.deque`	`unshift`, `shift` O(n) in general	`Insert(0, x)`, `RemoveAt(0)` O(n); use `Queue<T>` / `LinkedList<T>`
membership in a list	`x in xs` O(n)	`includes`, `indexOf` O(n)	`List.Contains` O(n)
membership in a set / map	`set`, `dict` O(1)	`Set`, `Map` O(1)	`HashSet`, `Dictionary` O(1)
sort	`sorted`, `list.sort` O(n log n), stable	`Array.prototype.sort` O(n log n), stable	`Array.Sort` O(n log n), unstable; LINQ `OrderBy` stable
copy a slice of length k	`xs[i:j]` O(k)	`slice` O(k)	`GetRange`, `[i..j]` on arrays O(k)
build a string from n pieces	`"".join(parts)` O(total)	`parts.join("")` O(total)	`StringBuilder` O(total)
heap push / pop	`heapq` O(log n), min-heap	no built-in heap	`PriorityQueue<TElement,TPriority>` O(log n)
ordered map insert / lookup	no built-in (`bisect` on a list is O(n) insert)	no built-in	`SortedDictionary`, `SortedSet` O(log n)

Variations you’ll meet

Several input sizes. A graph search is O(V + E), not O(n). Comparing every word of length L in a list of n words is O(n · L). Comparing n strings while sorting them is O(L · n log n), because each comparison can read L characters.
Output-sensitive bounds. Printing all pairs that match is O(n + output). Generating all subsets is O(2ⁿ · n), and nothing can beat the size of the output.
Recursive algorithms. Write the cost as a recurrence: merge sort is T(n) = 2T(n/2) + O(n) = O(n log n). The master theorem solves the common shapes. Naive Fibonacci is T(n) = T(n−1) + T(n−2) + O(1), which is exponential (about 1.618ⁿ).
Harmonic sums. for i in 1..n: for j in i, 2i, 3i, … ≤ n does n/1 + n/2 + n/3 + … ≈ n ln n steps: O(n log n), not O(n²). The sieve of Eratosthenes is a tighter cousin at O(n log log n).
Pseudo-polynomial time. A DP over a target value T costs O(n · T). That looks polynomial, but T is a number, so it’s exponential in the number of digits used to write it. It’s fine when T ≤ 10⁴, hopeless when T ≤ 10¹⁸. See knapsack.
Lower bounds. Any comparison sort needs Ω(n log n) comparisons (there are n! orderings and each comparison gives one bit). If someone asks for faster sorting, the answer uses structure in the values (counting sort, radix sort), not cleverer comparisons.

Pitfalls

Hidden linear calls in a loop. if x in some_list inside a loop over n items is O(n²). Same for JS includes/indexOf, C# List.Contains, Python list.pop(0), JS shift().
String building. Concatenating in a loop can copy the whole string each time: O(n²) total. CPython sometimes optimizes s += t in place, but don’t rely on it. Use join or StringBuilder.
Sorting inside a loop. Re-sorting after every insert is O(n² log n). Use a heap or an ordered structure instead.
Forgetting the stack. “O(1) space” is false for a recursive solution n levels deep.
Collapsing variables. Saying O(n) when the work is O(n + m) or O(n · k) hides exactly the part the interviewer wants to discuss.
Quoting a hash map’s average case as a guarantee. It’s average. If inputs can be adversarial (keys chosen by an attacker), say so; that’s why runtimes randomize string hashing.
Treating amortized as “usually fast”. Amortized is a worst-case guarantee for the sequence. If a single operation must be fast (a latency-sensitive request), O(n) occasional spikes may still matter.

In the interview

Before coding: read the constraints, back out the target complexity, and say it. “n ≤ 10⁵, so I want O(n log n) or better.”
After coding: state time and space, name every variable, and give the reason in one sentence. “O(n log n) for the sort, then a single O(n) pass; O(n) extra for the copy.”
When there’s a loop inside a loop, say whether the inner one is amortized: “the inner while looks quadratic, but left only moves forward, so it runs n times in total.”
When you use a hash map, say “expected O(1)” and be ready for “what’s the worst case?”.
Expect these follow-ups: “Can you do better?” (find the bottleneck step), “What if memory is limited?” (trade time back), “What if this is called 10⁶ times?” (precompute, cache), “What’s the lower bound?” (is the output itself that big? is it a comparison sort?).

Check yourself

pick one

for i in 1..n: for (j = i; j <= n; j += i) work(). What is the total time?

Check yourself

pick one

A dynamic array push is 'O(1) amortized'. What exactly does that promise?

Check yourself

pick one

The constraints say n ≤ 2·10⁵ and you have an O(n²) idea. In C#, roughly how long would it take, and what should you aim for?

Practice on your own

These are classic textbook exercises, not gym questions:

Give the time complexity of the sieve of Eratosthenes and explain where the log log n comes from.
Write element distinctness three ways (pairs, sort, set). Time each at n = 10³, 10⁴, 10⁵ and apply the doubling test.
Analyse naive recursive Fibonacci: count the calls for n = 10, 20, 30 and fit the growth rate.
Show that a stack with a multipop(k) operation does O(n) total work over any n operations.
Find the complexity of building a string by repeated concatenation in a loop, then fix it.

Go deeper

Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS), 4th ed.: ch. 3, “Characterizing Running Times”, and ch. 16, “Amortized Analysis” (aggregate, accounting and potential methods).
Sedgewick and Wayne, Algorithms, §1.4 “Analysis of Algorithms”: the doubling-ratio experiment and tilde notation.
Laaksonen, Competitive Programmer’s Handbook, ch. 2 “Time complexity”: the input-size estimation table.
Python wiki: TimeComplexity: the cost of every list, deque, dict and set operation in CPython.

Sorting and custom comparatorsThe O(n log n) workhorse, and the comparison lower bound.

Divide and conquerRecurrences, recursion trees and the master theorem.

Hash maps and setsThe most common way to turn O(n²) into O(n).

Memory efficiencyWhen the space column of your analysis is the real constraint.

Complexity analysis

The idea in plain words

See it

When to reach for it

Read the constraints backwards

How it works

Analysing code: the recipe

Amortized analysis: the average over a sequence

Best, average, worst, expected, amortized

Space complexity

Optimizing: the playbook

What it costs

Variations you’ll meet

Pitfalls

In the interview

Check yourself

Practice on your own

Go deeper

Related