Big-O notation · Commitwise

Two solutions pass all ten tests in a few milliseconds. In production, with a million users, one still answers in a tenth of a second and the other takes three hours. Nothing is wrong with the second one’s logic. It just does work that grows much faster than the data.

Big-O notation is how developers describe that growth in one short expression, like O(n) or O(n²). It’s the first thing an interviewer asks after you solve a problem, and the fastest way to see trouble before production does.

New to some of these? Open what you need, or skip ahead.

Basics:What are arrays and indexes?

An array is a row of values stored one after another: [5, 8, 2, 9]. Each position has an index, starting at 0: here 5 is at index 0 and 9 at index 3. The last index is always count - 1 (Swift) or size - 1 / length - 1 (Kotlin, Java, TypeScript).

Reading nums[2] is instant, whatever the array’s size. Reading an index that doesn’t exist (like nums[4] here) crashes with an “index out of range” error (in TypeScript it quietly gives undefined, a bug of its own), which is why loops usually go from 0 up to, but not including, the length.

Basics:What are functions and parameters?

A function is a named piece of code you can run again and again. It takes parameters (inputs) and can return a result:

Swift:   func add(_ a: Int, _ b: Int) -> Int { a + b }
Kotlin:  fun add(a: Int, b: Int): Int = a + b
Java:    static int add(int a, int b) { return a + b; }
TS:      function add(a: number, b: number): number { return a + b; }

Calling it, add(2, 3), runs the code with a = 2 and b = 3 and gives back 5. A function that belongs to a class is usually called a method.

Basics:What are lists, sets and maps?

Collections hold many values:

A list (Swift Array, Kotlin List, Java List, a TypeScript array) keeps items in order, and allows duplicates: ["Ana", "Ben", "Ana"].
A set holds each value at most once and answers “is this in it?” very quickly.
A map (Swift Dictionary, Kotlin, Java and TypeScript Map) stores values under keys: "Ana" → 30, looked up by the key.

Lists use indexes starting at 0: in ["a", "b", "c"], "a" is at index 0 and "c" at index 2.

Basics:What is recursion?

A recursive function calls itself on a smaller version of the problem, until it reaches a case small enough to answer directly (the base case):

countdown(3) → prints 3, calls countdown(2) → prints 2, calls countdown(1) → prints 1, calls countdown(0) → stops

Two rules keep it correct: always have a base case, and make sure every call gets closer to it. Each call waits on the call stack until the smaller call finishes, so very deep recursion (hundreds of thousands of levels) can run out of stack space.

Basics:What is hashing?

A hash is a number computed from a value, like a fingerprint: the same value always gives the same hash, and different values usually give different ones. "Ana".hashCode() (Java, Kotlin) or Swift’s Hashable produce it; JavaScript engines hash keys internally for Map and Set.

Hash maps and hash sets use the hash to decide where to store each key, so they can jump straight to it later instead of searching: that’s why looking up a key takes about one step. Two different keys can occasionally have the same hash (a collision); the map handles it, just a little slower.

Part Not started

What Big-O measures

Imagine finding a friend’s number in a printed phone book with a million names:

Read every page from the start: in the worst case, a million looks. Double the book, double the work. That’s O(n), “linear”.
Open in the middle, then the middle of the half that’s left, and so on: about 20 looks for a million names, 21 for two million. That’s O(log n), “logarithmic”.
Speed dial: one tap, no matter how many names. That’s O(1), “constant”.

Big-O doesn’t count seconds, because those depend on the phone and the reader. It describes how the amount of work grows when the input grows. n is the size of the input: the number of names, items in a list, characters in a string.

Big-O gives an asymptotic upper bound on growth: f(n) is O(g(n)) if f(n) ≤ c·g(n) for all n beyond some n₀. In interviews it usually means the worst case unless you say otherwise, and you’re expected to state time and space separately, to distinguish worst, average and amortized costs (hash maps, dynamic arrays), and to name every variable that matters (O(n·m), O(V + E)).

The useful part in practice is knowing the hidden costs of library calls in each language, and knowing when Big-O stops being the deciding factor: small n, constant factors and memory locality. Both are in the Detailed version.

The complexities you’ll meet

Big-O	Name	Example	Steps for n = 1,000,000
O(1)	constant	read `array[i]`, look up a key in a hash map	1
O(log n)	logarithmic	binary search in a sorted array	~20
O(n)	linear	one loop over the array	1,000,000
O(n log n)	linearithmic	sorting	~20,000,000
O(n²)	quadratic	comparing every pair	1,000,000,000,000
O(2ⁿ)	exponential	trying every subset	more than atoms in the universe

At a billion simple steps per second, O(n log n) finishes in 0.02 seconds and O(n²) in about 17 minutes. That gap is why interviewers care.

Counting halvings

Logarithms sound scary, but in code they almost always mean “the problem gets cut in half each step”:

Predict the output

What gets printed for n = 8?

var remaining = 8
var steps = 0
while remaining > 1 {
    remaining /= 2
    steps += 1
}
print(steps)

var remaining = 8
var steps = 0
while (remaining > 1) {
    remaining /= 2
    steps++
}
println(steps)

int remaining = 8;
int steps = 0;
while (remaining > 1) {
    remaining /= 2;
    steps++;
}
System.out.println(steps);

let remaining = 8;
let steps = 0;
while (remaining > 1) {
  remaining = Math.floor(remaining / 2);   // / alone would give fractions
  steps++;
}
console.log(steps);

Beyond Big-O

Big-O is the first filter, not the final answer:

Constants and locality. Iterating an array is several times faster than a linked list of the same length, both O(n), because arrays are contiguous and CPU caches prefetch them. A sorted Array with binary search often beats a HashMap for a few hundred elements.
Small n. Insertion sort beats O(n log n) sorts on a few dozen elements, which is why real sort implementations (TimSort on the JVM and in V8, a TimSort variant in Swift) use it for small runs.
Name every input. O(n + m) and O(n·m) matter when one input is small (a 5-item cart against a 1-million-item catalog).
Size vs value. An algorithm that loops up to the value of a number (for i in 0..<amount) is exponential in the number of digits: “pseudo-polynomial”. It matters for problems like coin change with huge amounts.
The real bottleneck. One extra network round trip or database query per item (the N+1 problem) costs more than any in-memory O(n²) on a few thousand items.

State time and space separately; say worst, average or amortized; name every input (O(n·m) vs O(n + m), O(V + E)).
Big-O is a filter: constants, memory locality, small n and I/O round trips (N+1 queries) often decide real performance. Looping up to a number’s value is pseudo-polynomial.

Check this part

What does Big-O describe?
It ignores the machine and constants and describes the growth rate.
Binary search halves the remaining range each step. About how many steps for 1,000,000 items?
log₂(1,000,000) ≈ 20. That's O(log n).
Both are O(n). Why is iterating an array usually much faster than a linked list?
Big-O ignores constants; memory locality is one of the biggest constants in practice.
A 5-item cart is checked against a 1,000,000-item catalog: for each cart item, a hash lookup. How do you state the complexity?
Name every input. Calling both "n" hides that one is tiny and the other huge, and whether building the map is part of the cost.

Big-O describes how the amount of work grows with the input, not seconds: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ). At a million items, the gap between them is milliseconds versus hours.

Part Not started

Reading complexity from code

Three loops, three complexities

// O(n): one pass over the array
func total(_ prices: [Int]) -> Int {
    var sum = 0
    for price in prices { sum += price }
    return sum
}

// O(n²): for each element, look at every element
func hasDuplicate(_ items: [Int]) -> Bool {
    for i in items.indices {
        for j in items.indices where j != i {
            if items[i] == items[j] { return true }
        }
    }
    return false
}

// O(log n): the remaining range halves every step
func halvings(_ n: Int) -> Int {
    var steps = 0, remaining = n
    while remaining > 1 { remaining /= 2; steps += 1 }
    return steps
}

// O(n): one pass over the list
fun total(prices: List<Int>): Int {
    var sum = 0
    for (price in prices) sum += price
    return sum
}

// O(n²): for each element, look at every element
fun hasDuplicate(items: List<Int>): Boolean {
    for (i in items.indices) {
        for (j in items.indices) {
            if (i != j && items[i] == items[j]) return true
        }
    }
    return false
}

// O(log n): the remaining range halves every step
fun halvings(n: Int): Int {
    var steps = 0
    var remaining = n
    while (remaining > 1) { remaining /= 2; steps++ }
    return steps
}

// O(n): one pass over the array
static int total(int[] prices) {
    int sum = 0;
    for (int price : prices) sum += price;
    return sum;
}

// O(n²): for each element, look at every element
static boolean hasDuplicate(int[] items) {
    for (int i = 0; i < items.length; i++) {
        for (int j = 0; j < items.length; j++) {
            if (i != j && items[i] == items[j]) return true;
        }
    }
    return false;
}

// O(log n): the remaining range halves every step
static int halvings(int n) {
    int steps = 0, remaining = n;
    while (remaining > 1) { remaining /= 2; steps++; }
    return steps;
}

// O(n): one pass over the array
function total(prices: number[]): number {
  let sum = 0;
  for (const price of prices) sum += price;
  return sum;
}

// O(n²): for each element, look at every element
function hasDuplicate(items: number[]): boolean {
  for (let i = 0; i < items.length; i++) {
    for (let j = 0; j < items.length; j++) {
      if (i !== j && items[i] === items[j]) return true;
    }
  }
  return false;
}

// O(log n): the remaining range halves every step
function halvings(n: number): number {
  let steps = 0;
  let remaining = n;
  while (remaining > 1) { remaining = Math.floor(remaining / 2); steps++; }
  return steps;
}

Four rules cover almost everything:

Loops multiply when nested. A loop of n inside a loop of n is n × n = O(n²).
Steps add when they follow each other. A loop, then another loop: O(n) + O(n) = O(2n), which is still O(n).
Drop constants. O(2n) and O(n + 5) are O(n). Big-O is about the shape of the growth, not the exact count.
Keep only the biggest term. O(n² + n) is O(n²): for large n, the n² part is all that matters.

Space complexity

Space complexity counts the extra memory an algorithm needs as the input grows, not counting the input itself:

A few variables, whatever the input size: O(1).
A set or map that may hold every element: O(n).
A copy of the array, or a new filtered list: O(n).
Recursion uses the call stack: a recursive function that goes n calls deep needs O(n) space, even without creating any collections.

In interviews, always say both: “O(n) time and O(n) space, because of the set.”

Practice: analyzing step by step

Here’s a function that finds which products in an order are out of stock. Let’s find its complexity the way you would in an interview.

Out-of-stock products

func outOfStock(order: [String], inStock: [String]) -> [String] {
    var missing: [String] = []
    for sku in order {                       // loop over the order: n
        if !inStock.contains(sku) {          // contains on an array: m
            missing.append(sku)              // append: O(1) amortized
        }
    }
    return missing.sorted()                  // sort the result: up to n log n
}

fun outOfStock(order: List<String>, inStock: List<String>): List<String> {
    val missing = mutableListOf<String>()
    for (sku in order) {                     // loop over the order: n
        if (sku !in inStock) {               // contains on a list: m
            missing.add(sku)                 // add: O(1) amortized
        }
    }
    return missing.sorted()                  // sort the result: up to n log n
}

static List<String> outOfStock(List<String> order, List<String> inStock) {
    List<String> missing = new ArrayList<>();
    for (String sku : order) {               // loop over the order: n
        if (!inStock.contains(sku)) {        // contains on a list: m
            missing.add(sku);                // add: O(1) amortized
        }
    }
    Collections.sort(missing);               // sort the result: up to n log n
    return missing;
}

function outOfStock(order: string[], inStock: string[]): string[] {
  const missing: string[] = [];
  for (const sku of order) {                 // loop over the order: n
    if (!inStock.includes(sku)) {            // includes on an array: m
      missing.push(sku);                     // push: O(1) amortized
    }
  }
  return missing.sort();                     // sort the result: up to n log n
}

Name the inputs. There are two: the order (n items) and the stock list (m items). Don’t call both “n”: they can be very different sizes.
Cost of the loop body. contains on a list is O(m); append is O(1). So one iteration is O(m).
Multiply by the loop. n iterations × O(m) = O(n·m).
Add the steps that follow. Sorting up to n items: O(n log n).
Total. O(n·m + n log n). Space: O(n) for missing.

The fix is the same as before: turn inStock into a set first (O(m) once), and the loop becomes O(n). The total drops to O(m + n log n).

Exerciseeasy

Contains Duplicate

Given an array of integers, return true if any value appears at least twice, and false if every element is distinct. Write three solutions and give the time and space complexity of each:

compare every pair,
sort first,
use a set.

[1, 2, 3, 1]  → true
[1, 2, 3, 4]  → false

›

After sorting, equal values sit next to each other. How many neighbors do you need to compare?

›

A set’s insert/add tells you whether the value was already there. The first time it says “already there”, you’re done.

SolutionTry it yourself firstTime O(n) with a setSpace O(n) with a set

// 1. Every pair: O(n²) time, O(1) space
func containsDuplicatePairs(_ nums: [Int]) -> Bool {
    for i in 0..<nums.count {
        for j in (i + 1)..<nums.count where nums[i] == nums[j] { return true }
    }
    return false
}

// 2. Sort first: O(n log n) time, O(n) space (sorted() makes a copy)
func containsDuplicateSorted(_ nums: [Int]) -> Bool {
    let sorted = nums.sorted()
    for i in sorted.indices.dropFirst() where sorted[i] == sorted[i - 1] { return true }
    return false
}

// 3. A set: O(n) time, O(n) space
func containsDuplicate(_ nums: [Int]) -> Bool {
    var seen = Set<Int>()
    for n in nums where !seen.insert(n).inserted { return true }
    return false
}

// 1. Every pair: O(n²) time, O(1) space
fun containsDuplicatePairs(nums: IntArray): Boolean {
    for (i in nums.indices) for (j in i + 1 until nums.size) if (nums[i] == nums[j]) return true
    return false
}

// 2. Sort first: O(n log n) time, O(n) space (sorted() makes a copy)
fun containsDuplicateSorted(nums: IntArray): Boolean {
    val sorted = nums.sorted()
    return (1 until sorted.size).any { sorted[it] == sorted[it - 1] }
}

// 3. A set: O(n) time, O(n) space
fun containsDuplicate(nums: IntArray): Boolean {
    val seen = HashSet<Int>()
    return nums.any { !seen.add(it) }
}

// 1. Every pair: O(n²) time, O(1) space
static boolean containsDuplicatePairs(int[] nums) {
    for (int i = 0; i < nums.length; i++)
        for (int j = i + 1; j < nums.length; j++)
            if (nums[i] == nums[j]) return true;
    return false;
}

// 2. Sort first: O(n log n) time, O(log n) to O(n) space (sorts the array in place)
static boolean containsDuplicateSorted(int[] nums) {
    Arrays.sort(nums);
    for (int i = 1; i < nums.length; i++) if (nums[i] == nums[i - 1]) return true;
    return false;
}

// 3. A set: O(n) time, O(n) space
static boolean containsDuplicate(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    for (int n : nums) if (!seen.add(n)) return true;
    return false;
}

// 1. Every pair: O(n²) time, O(1) space
function containsDuplicatePairs(nums: number[]): boolean {
  for (let i = 0; i < nums.length; i++)
    for (let j = i + 1; j < nums.length; j++)
      if (nums[i] === nums[j]) return true;
  return false;
}

// 2. Sort first: O(n log n) time, O(n) space (toSorted() makes a copy)
function containsDuplicateSorted(nums: number[]): boolean {
  const sorted = nums.toSorted((a, b) => a - b);   // without a comparator, numbers sort as strings
  return sorted.some((n, i) => i > 0 && n === sorted[i - 1]);
}

// 3. A set: O(n) time, O(n) space
function containsDuplicate(nums: number[]): boolean {
  const seen = new Set<number>();
  for (const n of nums) {
    if (seen.has(n)) return true;
    seen.add(n);
  }
  return false;
}

Three answers, three trade-offs. The set is the fastest; the pairs version uses no extra memory; sorting in place is in between, but changes the caller’s array, which you should mention (or copy first). Comparing options like this, out loud, is exactly what interviewers want to hear.

Amortized cost

Some operations are usually cheap and occasionally expensive. Amortized analysis averages the cost over a sequence:

Appending to a dynamic array (Swift Array, ArrayList, Kotlin MutableList, a JavaScript array’s push): when capacity runs out, the array allocates about twice the space and copies everything, O(n). Because capacity doubles, n appends cost O(n) in total, so each is O(1) amortized. Reserve capacity (reserveCapacity, ArrayList(n)) when you know the size, to skip the copies.
Hash map inserts are O(1) amortized for the same reason (rehashing when the load factor is exceeded), and O(1) average only with a good hash.

Amortized O(1) is not “every call is fast”: a latency-sensitive path (a frame render, a request at p99.9) can still hit the one O(n) resize.

Exercisemedium

The nightly report that stopped finishing

A nightly job builds a sales report. It ran in 2 minutes a year ago; now it doesn’t finish before morning. The data grew from 10,000 to 200,000 orders, 50,000 customers and 5,000 products.

fun buildReport(orders: List<Order>, customers: List<Customer>, products: List<Product>): List<ReportLine> {
    val lines = mutableListOf<ReportLine>()
    for (order in orders) {
        val customer = customers.first { it.id == order.customerId }
        var total = 0.0
        for (line in order.lines) {                                   // ~3 lines per order
            val product = products.first { it.sku == line.sku }
            total += product.price * line.quantity
        }
        lines.add(ReportLine(customer.name, order.id, total))
        lines.sortByDescending { it.total }
    }
    return lines
}

What is its time complexity? Name every variable.
Estimate the work now compared with a year ago.
Fix it, and give the new complexity.

›

There are three costs inside the order loop: a search through customers, a search through products per line, and a sort that runs on every iteration.

›

Build lookup maps once before the loop, and sort once after it. Check what the old customer count probably was before comparing.

SolutionTry it yourself firstTime O(o + c + p + o log o)Space O(c + p + o)

Before, with o orders, c customers, p products and ~3 lines per order:

customer search: O(o · c)
product search: O(o · 3 · p)
sorting inside the loop: the list has 1, 2, …, o items, so Σ k log k = O(o² log o)

Total: O(o·c + o·p + o² log o). The sort dominates: at o = 200,000 that’s on the order of 200,000² × 17 ≈ 7 × 10¹¹ comparisons, versus about 10⁹ for 10,000 orders a year ago. The data grew 20×, the work grew roughly 500×.

func buildReport(orders: [Order], customers: [Customer], products: [Product]) -> [ReportLine] {
    let customerByID = Dictionary(uniqueKeysWithValues: customers.map { ($0.id, $0) })
    let productBySKU = Dictionary(uniqueKeysWithValues: products.map { ($0.sku, $0) })

    return orders.map { order in
        let customer = customerByID[order.customerID]!                // data integrity: fail loudly
        let total = order.lines.reduce(0.0) { $0 + productBySKU[$1.sku]!.price * Double($1.quantity) }
        return ReportLine(customerName: customer.name, orderID: order.id, total: total)
    }
    .sorted { $0.total > $1.total }
}

fun buildReport(orders: List<Order>, customers: List<Customer>, products: List<Product>): List<ReportLine> {
    val customerById = customers.associateBy { it.id }                // O(c)
    val productBySku = products.associateBy { it.sku }                // O(p)

    return orders.map { order ->                                      // O(o)
        val customer = customerById.getValue(order.customerId)
        val total = order.lines.sumOf { productBySku.getValue(it.sku).price * it.quantity }
        ReportLine(customer.name, order.id, total)
    }.sortedByDescending { it.total }                                 // once: O(o log o)
}

static List<ReportLine> buildReport(List<Order> orders, List<Customer> customers, List<Product> products) {
    Map<Long, Customer> customerById = customers.stream()
        .collect(Collectors.toMap(Customer::id, c -> c));
    Map<String, Product> productBySku = products.stream()
        .collect(Collectors.toMap(Product::sku, p -> p));

    return orders.stream()
        .map(order -> {
            Customer customer = customerById.get(order.customerId());
            double total = order.lines().stream()
                .mapToDouble(l -> productBySku.get(l.sku()).price() * l.quantity())
                .sum();
            return new ReportLine(customer.name(), order.id(), total);
        })
        .sorted(Comparator.comparingDouble(ReportLine::total).reversed())
        .toList();
}

function buildReport(orders: Order[], customers: Customer[], products: Product[]): ReportLine[] {
  const customerById = new Map(customers.map((c) => [c.id, c]));      // O(c)
  const productBySku = new Map(products.map((p) => [p.sku, p]));      // O(p)

  return orders
    .map((order) => {                                                   // O(o)
      const customer = customerById.get(order.customerId)!;
      const total = order.lines.reduce((sum, l) => sum + productBySku.get(l.sku)!.price * l.quantity, 0);
      return { customerName: customer.name, orderId: order.id, total };
    })
    .sort((a, b) => b.total - a.total);                                 // once: O(o log o)
}

After: O(c + p) to build the maps, O(o) for the loop (3 O(1) lookups per order), O(o log o) for one sort. That’s a few million operations: seconds, not hours.

What to add in a real review: money should be in integer minor units, not Double; with millions of orders, do the join and the sort in the database (JOIN + ORDER BY, with an index) and stream the result instead of loading every order into memory; and add a test with production-sized data, because the bug was invisible at 10,000 rows.

Deep dives

Deep diveThe master theorem in one minuteInterview favorite

Divide-and-conquer algorithms have running times like T(n) = a·T(n/b) + f(n): a subproblems of size n/b, plus f(n) work to split and combine. Compare f(n) with n^(log_b a), the work done at the leaves:

Merge sort: T(n) = 2T(n/2) + n. Both are n, so every level costs n and there are log n levels: O(n log n).
Binary search: T(n) = T(n/2) + 1. One subproblem, constant work: O(log n).
Visiting every node of a balanced tree: T(n) = 2T(n/2) + 1. The leaves dominate: O(n).

You rarely need the formal statement in an interview; drawing the recursion tree and summing each level gets the same answers.

Amortized O(1) (dynamic array append, hash map insert) averages occasional O(n) resizes over a sequence; a single call can still be slow, which matters at p99.9.
Analyze inside out: the loop body’s cost (including library calls), times the iterations, plus whatever follows. A sort inside a loop is O(n² log n).

Check this part

A loop over n items contains another loop over n items. What is the complexity?
Nested loops multiply: n × n.
How do you write O(3n + n² + 10) in Big-O?
Drop constants and keep only the fastest-growing term.
Why is appending to a dynamic array O(1) amortized even though it sometimes copies everything?
Growing by a factor makes the expensive resizes rare enough to average out to O(1).
A loop over o orders sorts the growing result list on every iteration. What does the sorting alone cost?
Σ k log k for k = 1…o is O(o² log o). Sort once, after the loop.

Nested loops multiply, steps in sequence add, constants and smaller terms are dropped. Name every input, count the loop body's cost (including library calls), and state space as well as time.

Part Not started

The loop that hides a loop

The code below looks like one loop. It isn’t. Where’s the second one?

Spot the bugRemoving duplicate emails

Tap the line with the bug.

func uniqueEmails(_ emails: [String]) -> [String] {
    var result: [String] = []
    for email in emails {
        if !result.contains(email) {
            result.append(email)
        }
    }
    return result
}

fun uniqueEmails(emails: List<String>): List<String> {
    val result = mutableListOf<String>()
    for (email in emails) {
        if (email !in result) {
            result.add(email)
        }
    }
    return result
}

static List<String> uniqueEmails(List<String> emails) {
    List<String> result = new ArrayList<>();
    for (String email : emails) {
        if (!result.contains(email)) {
            result.add(email);
        }
    }
    return result;
}

function uniqueEmails(emails: string[]): string[] {
  const result: string[] = [];
  for (const email of emails) {
    if (!result.includes(email)) {
      result.push(email);
    }
  }
  return result;
}

contains (or includes) on a list checks every element, one by one: it’s a loop of up to n steps, inside a loop of n steps. The function is O(n²). With 100 emails nobody notices; with a mailing list of 200,000 it’s 20 billion comparisons.

Remember what you’ve seen in a set, which answers contains in O(1) on average. Keep the list for the order:

func uniqueEmails(_ emails: [String]) -> [String] {
    var seen = Set<String>()
    return emails.filter { seen.insert($0).inserted }   // insert returns whether it was new
}

fun uniqueEmails(emails: List<String>): List<String> = emails.distinct()   // uses a set internally

// or by hand:
// val seen = HashSet<String>(); emails.filter { seen.add(it) }

static List<String> uniqueEmails(List<String> emails) {
    return new ArrayList<>(new LinkedHashSet<>(emails));   // a set that keeps insertion order
}

function uniqueEmails(emails: string[]): string[] {
  return [...new Set(emails)];   // a Set keeps insertion order
}

Now it’s O(n) time, and O(n) extra space for the set: a typical trade of memory for speed.

Hidden costs in everyday calls

The biggest source of slow code isn’t a missing algorithm; it’s a library call that’s more expensive than it looks:

Call	Cost	Why
`contains` / `indexOf` / `includes` on a list or array	O(n)	checks elements one by one
`shift()` / `unshift()` / `splice(0, …)` on a TypeScript array	O(n)	the remaining elements are re-indexed
`[...items, x]` or `concat` in a loop (TypeScript)	O(n) each time	every spread copies the whole array
`removeFirst()` / `remove(at: 0)` on Swift `Array`, `removeAt(0)` / `remove(0)` on `ArrayList`	O(n)	every other element moves one place left
`insert(x, at: 0)` / `add(0, x)` on an array list	O(n)	every element moves one place right
`s = s + piece` in a loop (Kotlin, Java)	O(length) each time	strings are immutable, so each `+` copies everything so far
`get(i)` on Java’s `LinkedList`	O(n)	walks from the nearest end
`count` on a Swift `String`	O(n)	characters have variable size, so it counts them
`sort` / `sorted`	O(n log n)	never “free”, even when it’s one word

Building a string

Predict the output

What is the time complexity of build(pieces) for n pieces of similar length?

func build(_ pieces: [String]) -> String {
    var result = ""
    for piece in pieces {
        result += piece
    }
    return result
}

fun build(pieces: List<String>): String {
    var result = ""
    for (piece in pieces) {
        result += piece
    }
    return result
}

static String build(List<String> pieces) {
    String result = "";
    for (String piece : pieces) {
        result += piece;
    }
    return result;
}

function build(pieces: string[]): string {
  let result = "";
  for (const piece of pieces) {
    result += piece;
  }
  return result;
}

A queue that isn’t

Spot the bugA job processor that slows to a crawl

Tap the line with the bug.

func process(_ jobs: [Job]) {
    var queue = jobs
    while !queue.isEmpty {
        let job = queue.removeFirst()
        queue.append(contentsOf: job.run())   // a job can create follow-up jobs
    }
}

fun process(jobs: List<Job>) {
    val queue = jobs.toMutableList()
    while (queue.isNotEmpty()) {
        val job = queue.removeAt(0)
        queue.addAll(job.run())                // a job can create follow-up jobs
    }
}

static void process(List<Job> jobs) {
    List<Job> queue = new ArrayList<>(jobs);
    while (!queue.isEmpty()) {
        Job job = queue.remove(0);
        queue.addAll(job.run());               // a job can create follow-up jobs
    }
}

function process(jobs: Job[]) {
  const queue = [...jobs];
  while (queue.length > 0) {
    const job = queue.shift()!;
    queue.push(...job.run());               // a job can create follow-up jobs
  }
}

Removing the first element of an array shifts every remaining element one slot left: O(n) per removal, O(n²) to drain the queue. With 100,000 queued jobs that’s about 5 billion element moves, and it gets worse exactly when the system is busiest (a long queue).

Use a real double-ended queue, O(1) at both ends:

import DequeModule                              // swift-collections

var queue = Deque(jobs)
while let job = queue.popFirst() {
    queue.append(contentsOf: job.run())
}

// Without the package: keep a read index instead of removing.
// var head = 0; while head < queue.count { let job = queue[head]; head += 1; … }

val queue = ArrayDeque(jobs)
while (queue.isNotEmpty()) {
    val job = queue.removeFirst()               // O(1) on ArrayDeque
    queue.addAll(job.run())
}

Deque<Job> queue = new ArrayDeque<>(jobs);
while (!queue.isEmpty()) {
    Job job = queue.pollFirst();                // O(1) on ArrayDeque
    queue.addAll(job.run());
}

// No built-in deque: keep a read index instead of shift().
const queue = [...jobs];
for (let head = 0; head < queue.length; head++) {
  queue.push(...queue[head].run());           // O(1) per job; drop the processed prefix now and then if memory matters
}

Kotlin’s MutableList.removeFirst() has the same name as ArrayDeque.removeFirst() but is O(n) on an ArrayList. The type matters more than the method name. In TypeScript, engines sometimes optimize shift() on small arrays, but nothing guarantees it for a long queue.

Operation	Swift	Kotlin	Java	TypeScript
Index access	`Array` O(1)	`ArrayList` O(1)	`ArrayList` O(1), `LinkedList` O(n)	array O(1)
Append	O(1) amortized	O(1) amortized	O(1) amortized	`push` O(1) amortized
Remove/insert at front	`Array` O(n), `Deque` O(1)	`ArrayList` O(n), `ArrayDeque` O(1)	`ArrayList` O(n), `ArrayDeque` O(1)	`shift`/`unshift` O(n), no built-in deque
Contains	`Array` O(n), `Set` O(1) avg	`List` O(n), `HashSet` O(1) avg	`List` O(n), `HashSet` O(1) avg	`includes` O(n), `Set.has` O(1) avg
Sorted container ops	— (no built-in sorted set)	`TreeMap`/`TreeSet` O(log n)	`TreeMap`/`TreeSet` O(log n)	— (no built-in sorted set)
Sort	O(n log n) (a TimSort variant)	O(n log n) (TimSort, stable)	O(n log n) (TimSort for objects, dual-pivot quicksort for primitives)	O(n log n) (TimSort in V8, stable; compares as strings without a comparator)
String length	`count` O(n), `utf8.count` O(1)	O(1)	O(1)	`length` O(1) (UTF-16 units)
Build a string in a loop	`+=` on `var` O(1) amortized	`buildString` / `StringBuilder`	`StringBuilder`	`+=` (ropes in V8) or `join`

Watch for: contains/indexOf in loops, front removals on arrays, string += on the JVM, copying spreads in loops, sorting inside loops, N+1 queries.

The usual fix: a set or map built once

let blocked = Set(blockedIDs)                        // O(m) once
let visible = posts.filter { !blocked.contains($0.authorID) }   // O(n)

val blocked = blockedIds.toHashSet()                  // O(m) once
val visible = posts.filter { it.authorId !in blocked }          // O(n)

Set<Long> blocked = new HashSet<>(blockedIds);        // O(m) once
List<Post> visible = posts.stream().filter(p -> !blocked.contains(p.authorId())).toList();   // O(n)

const blocked = new Set(blockedIds);                  // O(m) once
const visible = posts.filter((p) => !blocked.has(p.authorId));   // O(n)

Check this part

What is the complexity of result.contains(email) inside a loop over the emails, when result is an array?What is the complexity of email !in result inside a loop over the emails, when result is a list?What is the complexity of result.contains(email) inside a loop over the emails, when result is a list?What is the complexity of result.includes(email) inside a loop over the emails, when result is an array?
Searching a list is itself a loop. Use a set for O(1) average lookups.
What does switching the "seen" list to a set cost?
A typical trade of memory for speed. Keep a list (or an ordered set) when the order matters.
A job queue is an Array drained with removeFirst(). Draining n jobs costs…A job queue is an ArrayList drained with removeAt(0). Draining n jobs costs…A job queue is an ArrayList drained with remove(0). Draining n jobs costs…A job queue is an array drained with shift(). Draining n jobs costs, without relying on engine tricks…
Every removal shifts the rest. Use Deque from swift-collections, or a read index.Every removal shifts the rest. Use ArrayDeque.shift() re-indexes the remaining elements. Keep a read index (or use a ring buffer) instead.
n pieces of similar length are joined with result += piece in a loop. What is the complexity?
A uniquely referenced var String appends in place: amortized O(1) per append.Strings are immutable: each += copies everything so far. Use buildString or joinToString.Strings are immutable: each += copies everything so far. Use one StringBuilder or String.join.Engines like V8 build a rope and flatten it once, so it's O(n) in practice; pieces.join("") is the portable choice.

The slowest code usually hides a loop inside a library call: contains on a list, removing from the front of an array, building strings or arrays by copying. Know each call's cost in your language.

Key takeaways

Big-O describes how work grows with the input: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ).
Nested loops multiply, sequential steps add, constants and smaller terms are dropped.
Library calls have costs: contains on a list is a hidden loop, so use a set or map for lookups.
Always state time and space complexity, and compare solutions out loud.

Distinguish worst, average and amortized cost, and name every input variable (O(n·m) vs O(n + m)).
Know each language’s hidden costs: array front removals (shift), JVM string concatenation, Swift String.count, copying spreads and sorts in loops.
Big-O is a filter: locality, constants, small n and I/O round trips often decide real performance.
Test with production-sized data: quadratic code is invisible at small n.