No history yet

Asymptotic Complexity Analysis

Beyond the Stopwatch

How do you know if your code is fast? You could time it with a stopwatch, but that's a flawed approach. The same Java code might run faster on a new laptop than on an old desktop. Even on the same machine, the first run might be slower than the second because of how the Java Virtual Machine (JVM) warms up and optimises code.

To compare algorithms fairly, we need a method that ignores the hardware and specific runtime environment. This is where asymptotic analysis comes in. It provides a mathematical way to describe an algorithm's efficiency as its input size grows infinitely large. We're not measuring seconds; we're measuring how the number of operations scales with the input.

Complexity analysis helps us understand how fast (or slow) an algorithm will run as its input size grows.

This analysis focuses on two key resources: time and space.

  • Time Complexity: How the runtime of an algorithm scales with the input size, nn.
  • Space Complexity: How the amount of memory an algorithm needs scales with the input size, nn.

We use a special set of notations to describe these complexities, focusing on the worst-case, best-case, and average-case scenarios.

The Language of Growth

To talk about how complexity grows, we use three main notations from a family called asymptotic notations. They give us a language to define performance boundaries.

Big O

noun

Describes the upper bound of an algorithm's complexity. It tells us the worst-case scenario, guaranteeing that the algorithm's performance will not exceed a certain level.

Big O is the most common notation you'll encounter. When someone mentions the 'complexity' of an algorithm, they're usually talking about its Big O performance.

T(n)=O(f(n))T(n) = O(f(n))

Next, we have Big Omega, which is the flip side of Big O.

Big Omega

noun

Describes the lower bound of an algorithm's complexity. It represents the best-case scenario, guaranteeing the algorithm will take at least a certain amount of time or space.

T(n)=Ω(f(n))T(n) = \Omega(f(n))

Finally, when an algorithm's upper and lower bounds are the same, we use Big Theta.

Big Theta

noun

Describes a tight bound on an algorithm's complexity. It's used when the best-case and worst-case performance grow at the same rate.

T(n)=Θ(f(n))T(n) = \Theta(f(n))

The graph shows how for an input size greater than n0n_0, the actual function f(n)f(n) is sandwiched between the upper bound of Big O and the lower bound of Big Omega. When both bounds apply with the same growth function g(n)g(n), we can say the algorithm is Θ(g(n))\Theta(g(n)).

Analysing Java Code

Let's apply these concepts to Java. When analysing code, we count the number of basic operations (assignments, comparisons, arithmetic operations) relative to the input size nn.

The key is to ignore constant factors and lower-order terms. An algorithm that takes 3n2+100n+503n^2 + 100n + 50 operations is simplified to O(n2)O(n^2), because as nn becomes very large, the n2n^2 term dominates everything else.

Consider a simple loop that finds the maximum value in an array.

int findMax(int[] array) {
    int max = array[0]; // 1 operation
    // Loop runs n times
    for (int i = 1; i < array.length; i++) {
        // 1 comparison per iteration
        if (array[i] > max) {
            max = array[i]; // 1 assignment (worst case)
        }
    }
    return max; // 1 operation
}

Here, the loop is the dominant part of the algorithm. It runs n−1n-1 times, where nn is the length of the array. Inside the loop, we have a comparison and a potential assignment. The total number of operations is roughly proportional to nn. Therefore, the time complexity is Θ(n)\Theta(n). We use Theta because you always have to check every element, making the best and worst cases the same.

What about nested loops? They often lead to polynomial complexity.

void printPairs(int[] array) {
    // Outer loop runs n times
    for (int i = 0; i < array.length; i++) {
        // Inner loop runs n times
        for (int j = 0; j < array.length; j++) {
            System.out.println(array[i] + "," + array[j]);
        }
    }
}

The inner loop executes nn times for each execution of the outer loop. Since the outer loop also runs nn times, the total number of print operations is n×n=n2n \times n = n^2. The time complexity is Θ(n2)\Theta(n^2). The space complexity for both examples is O(1)O(1) (or constant), because we only use a fixed number of variables regardless of the array size.

Recursion and Amortised Analysis

Analysing recursive functions involves setting up a recurrence relation. A classic example is the factorial function.

long factorial(int n) {
    // Base case
    if (n <= 1) {
        return 1;
    }
    // Recursive step
    return n * factorial(n - 1);
}

Let T(n)T(n) be the time to compute factorial(n). The function does a constant amount of work (a comparison and a multiplication) and then calls itself with n−1n-1. This gives us the recurrence relation:

T(n)=T(n−1)+cT(n) = T(n-1) + c

Solving this relation shows that the total work is proportional to nn. Thus, the time complexity is O(n)O(n). Each recursive call also adds a frame to the call stack, so the space complexity is also O(n)O(n).

Sometimes, an operation can be very expensive, but it happens so rarely that its cost, when averaged over a sequence of operations, is small. This is the idea behind amortised analysis.

Amortised analysis gives the average performance of each operation in the worst case, over a sequence of operations.

A great example is Java's ArrayList. When you add an element, it usually takes constant time, O(1)O(1). But if the internal array is full, ArrayList must create a new, larger array and copy all the old elements over. This single add operation is expensive—it takes O(n)O(n) time, where nn is the current size.

However, because the array size is typically doubled each time it resizes, these expensive O(n)O(n) operations happen infrequently. When you average the cost over many additions, the cost per operation comes out to be constant. We say the add operation has an amortised time complexity of O(1)O(1).

Ready to test your understanding?

Quiz Questions 1/6

Why is timing code with a stopwatch an unreliable method for comparing algorithm efficiency across different machines?

Quiz Questions 2/6

What does Big O notation (e.g., O(n2)O(n^2)) primarily describe about an algorithm?

Understanding asymptotic analysis is fundamental to writing scalable and efficient software. It allows you to make informed decisions about which algorithms and data structures to use, which is a crucial skill in software engineering.