Lesson 1 · Foundations

Time and Space Complexity

Complexity lets us compare algorithms without depending on one computer or programming language. It tells us how a solution scales.

Why complexity is useful

When solving a problem, there are often many correct approaches. However, a solution that takes 2 milliseconds on a list of 10 items might take a week on a list of a million items.

Time and space complexity give us a mathematical way to describe how an algorithm scales as the input size (usually called N) grows, independent of CPU speed or programming language.

Focus on the rate of growth, not exact seconds
Allows objective comparison between algorithms
Helps predict performance crashes at scale

Big-O Notation

Big-O notation describes an asymptotic upper bound on growth. It is often used when reporting a worst-case running time, but Big-O itself does not mean worst case; best, average, and worst case describe which inputs or executions are being analysed.

When calculating Big-O, we drop constant factors and lower-order terms. For example, if an algorithm takes 3N + 5 operations, we simply call it O(N) because the linear N term dominates as N becomes large.

O(1): Constant time (always takes the same time)
O(log N): Logarithmic time (input is halved each step)
O(N): Linear time (time scales directly with input)

Key reference

Terms, operations, and practical uses

Growth rates

O(1)The amount of work does not grow with the input.
O(log n)Each operation removes a fixed portion of the remaining input.
O(n)The algorithm performs work proportional to the input size.

Analysis rules

Sequential workAdd separate costs and retain the fastest-growing term.
Nested workMultiply loop counts when one loop runs completely inside another.
Worst caseDescribe the most work required by a valid input.

Practical examples

Array indexingReading a known array position is O(1).
Linear searchAn unsuccessful search may inspect all n values.
Binary searchA valid comparison discards half of the remaining ordered range.

Code example

Trace the work performed by linear search

def linear_search(values, target):
    for index, value in enumerate(values):
        if value == target:
            return index
    return -1
print(linear_search([4, 8, 12, 16], 12))

int linearSearch(vector<int>& values, int target) {
    for (int i = 0; i < values.size(); i++) {
        if (values[i] == target) return i;
    }
    return -1;
}

static int linearSearch(int[] values, int target) {
    for (int i = 0; i < values.length; i++) {
        if (values[i] == target) return i;
    }
    return -1;
}

Inputvalues = [4, 8, 12, 16], target = 12

Output2

Example

Run the example step by step

Output

Time complexity

Time complexity measures the number of fundamental operations an algorithm performs. The most common operations to count are comparisons, arithmetic, and assignments.

A single loop that iterates over an array of size N takes O(N) time. If you place a loop inside another loop (a nested loop), and both iterate N times, the inner code runs N * N times, resulting in O(N²) quadratic time.

Sequential loops add together: O(N) + O(N) = O(N)
Nested loops multiply: O(N) * O(N) = O(N²)
Function calls inside loops multiply by the function's complexity

Space complexity

Total space complexity includes the input representation and additional memory. Auxiliary space counts only the extra memory used by the algorithm, which is usually the quantity stated when comparing two solutions.

Auxiliary arrays, hash maps, and the implicit recursion stack all count as extra memory. Many iterative in-place algorithms use O(1) auxiliary space, but an in-place recursive algorithm may still consume O(log N) or O(N) stack space.

Many iterative in-place modifications use O(1) extra space
Allocating a new array of size N requires O(N) space
Recursive calls consume stack memory, often O(N) or O(log N)

How to analyse code

To analyze an algorithm, first identify the input size, N. Then, locate the most frequently executed line of code (often inside the deepest loop).

Count how many times that line executes relative to N. Then, identify any extra data structures you are creating and measure their maximum size relative to N.

Identify the input size (N, M, etc.)
Find the repeated operation
Count the iterations
Drop constants and lower-order terms

Common pitfalls

A common mistake is confusing multiple inputs. If you iterate over an array of size N and then an array of size M, the complexity is O(N + M), not O(N).

Another pitfall is ignoring hidden costs. Built-in functions like sorting an array (O(N log N)) or slicing a string (O(N)) take time and space, even if they look like a single line of code.

Don't collapse distinct inputs (N and M)
Remember the cost of built-in functions
String concatenations in loops can cost O(N²)