Time and Space Complexity

Algorithms

An algorithm is a method for solving a problem, made up of a sequence of steps. An algorithm has five characteristics:

1. Finiteness: The algorithm must terminate after a finite number of steps.
2. Definiteness: Every step of the algorithm must have a precise definition.
3. Input: An algorithm has zero or more inputs.
4. Output: An algorithm has one or more outputs. An algorithm with no output is meaningless.
5. Effectiveness: Every step performed by the algorithm can be broken down into basic executable operations.

Time Complexity

Some algorithms are efficient; others are clumsy. Time complexity and space complexity are two standards for evaluating an algorithm.

Imagine that a manager asks Xiao Hui and Da Huang to complete the same requirement. Both deliver code with the same functionality. Da Huang's code takes 100 ms and uses 5 MB of memory per run, while Xiao Hui's takes 100 seconds and uses 500 MB.

“Xiao Hui, pack your things. You don't need to come in tomorrow!”

Although Xiao Hui implemented the required functionality, his code has serious problems: it runs for too long and occupies too much space.

The time complexity of an algorithm describes the number of basic operations it performs. Basic operations include addition, subtraction, swapping, and comparison.

An algorithm's efficiency should depend on the algorithm itself rather than on a particular machine. When analyzing efficiency, we consider the relationship between running time and input size. Counting the basic operations gives us a function of the input size $n$.

Time complexity generally uses Big-O notation to express how running time grows with input size. Common complexities include $O(1)$, $O(\log n)$, $O(n)$, $O(n\log n)$, $O(n^2)$, $O(2^n)$, and $O(n!)$.

Apply these principles when simplifying time complexity:

1. If the running time is constant, write it as $O(1)$.
2. Keep only the highest-order term in the time function.
3. Remove the coefficient of the highest-order term.

Big-O notation

Big-O notation represents an upper bound on time complexity, often used to discuss the worst case. The order of the algorithm does not exceed the function $g(n)$ in the Big-O bound.

Big-$\Omega$ notation

Big-$\Omega$ notation represents a lower bound on time complexity, often used to discuss the best case. The order of the algorithm is not lower than the function $g(n)$ in the Big-$\Omega$ bound.

Little-o notation

Little-o notation represents a strict upper bound: the algorithm's order is strictly lower than the function $g(n)$ in the bound.

Little-$\omega$ notation

Little-$\omega$ notation represents a strict lower bound: the algorithm's order is strictly higher than the function $g(n)$ in the bound.

$\Theta$ notation

If $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$, then $f(n)$ and $g(n)$ have the same order:

One hundred chickens for one hundred coins

A rooster costs 5 coins, a hen costs 3 coins, and three chicks cost 1 coin. If 100 coins must buy exactly 100 chickens, how many roosters, hens, and chicks should be purchased?

#include <stdio.h>

void buy(int n, int money) {
    for (int x = 0; x <= n / 5; x++) {
        for (int y = 0; y <= n / 3; y++) {
            int z = n - x - y;
            if (z > 0 && z % 3 == 0 && 5 * x + 3 * y + z / 3 == money) {
                printf("x = %d, y = %d, z = %d\n", x, y, z);
            }
        }
    }
}

int main() {
    buy(100, 100);
    return 0;
}

Space Complexity

The less memory an algorithm occupies, the better. Space complexity measures the temporary storage space used while an algorithm runs, and it also uses Big-O notation.

You cannot always have the best of both worlds. Time and space complexity often require a trade-off. In most situations, time complexity is more important: it is worth allocating some additional memory to improve execution speed.

Amortized Time Complexity

Amortized time complexity analyzes a sequence of operations in which an individual operation may be expensive, but the average cost across the sequence remains low.

Dynamic arrays

void add(DynamicArray *list, int element) {
    if (list->size == list->capacity) {
        list->capacity *= 2;
        list->arr = realloc(list->arr, list->capacity * sizeof(int));
    }
    list->arr[list->size++] = element;
}

This code adds data to an array. When the array is not full, it places the new element directly at the end, which takes $O(1)$ time.

When the array is full, however, it must create a larger array, copy the original data into it, and then add the new element at the end. This process takes $O(n)$ time.

Suppose the array has capacity $n$ and expands only once for every $n$ calls to add(). We can spread that one $O(n)$ cost across the preceding $n$ operations, making the amortized time complexity of add() equal to $O(1)$.