Although complexity of algorithms is a theoretical subject that is 99.9% of the time not used in real world, it is worth to refresh knowledge on it. Classifying the behaviour of an implemented algorithm can come in hand when analysing performance issues or designing more efficient algorithms.
Basic concepts
Input
The input to an algorithm, typically defined by \(n\\). The size of the input is defined based on the type of data: number of items for arrays, number of bits for files, or characterisation of graphs or trees and so on.
Running time
The running time or time complexity of an algorithm estimates the time taken to run the algorithm based on the size of a particular input. It is common to define the running time as a function of the size of its input, or \(T(n)\\).
Examples of the formula defined by the running time can be \(T(n) = 2T(\frac{n}{2}) + cn\\) or \(T(n) = (n-1)T(n-1) + bn + c\\).
To better identify the implications of an algorithm, it is common to analyse how it behaves under best, average and worst case scenarios (all of them quite dependant on the algorithm):
- Best-case running time: behaviour under optimal conditions. E.g., a linear search algorithm finds the element on the first position
- Average running time: typical behaviour. This can be difficult to measure, but could be something like a pseudo-randomly generated array generated by a *nix distribution
- Worst-case running time: behaviour under non-convenient conditions. E.g., insertion sort finds the input reversed sorted
For some algorithms, the worst case occurs fairly often. In other cases, it will be more interesting to focus on the average case. It is then possible that under some constraints it is preferable to pick an algorithm with better performance on average time than other, even at the cost of a worst performance on the worst-case scenario. Such would be the case of quicksort when compared to others such as a mergesort or heapsort.
Some of the most common running times, in increasing order of time, are described in the table below.
| Name | Running time |
|---|---|
| Logarithmic | \(\theta(lg \hspace{0.5em} n)\\) |
| Constant | \(\theta(1)\\) |
| Linear | \(\theta(n)\\) |
| Quadratic | \(\theta(n^2)\\) |
| Cubic | \(\theta(n^3)\\) |
| Exponential | \(2^{\theta(n)}\\) |
| Factorial | \(\theta(n!)\\) |
Rate of growth
The order/rate of growth \(\theta(n)\) of the running time performs a simple estimation of the algorithm’s efficiency. This is obtained by considering the leading terms of the formula from the running time and ignoring lower-order terms and constants, which are negligible in comparison.
Examples of the formula defined by the rate of growth of the running time can be \(\theta(n\hspace{.2em}lg(n))\\) or \(\theta(n^2)\\).
Space complexity
The space complexity of an algorithm estimates the usage of the memory space based on the size of a particular input.
Though it does not seem as popular as the time complexity analysis, identifying the memory space used by the computer can be useful to troubleshoot and improve performance of algorithms dealing with large sets of data to be delivered by some client.
Asymptotic notation
The asymptotic efficiency of an algorithm analyses the trend of the running time when as the size of the input increases without bond, to a limit. This concept also operates over mathematical functions and is depicted plotting different functions over a bi-dimensional graph (X=size of input, Y=running time).
These asymptotic notation is used to formalise the running time of an algorithm. Each notation provides different bounds \(g(n)\\) to a given function \(f(n)\\), so analysis is performed for different scenarios and input sizes. The upper and lower bound represent the lowest (best) and highest (worst) running times, specifically. More details here and here.
- \(\theta\\)-notation: provides upper and lower asymptotically tight bounds; so that \(c_1 g(n) \geq f(n) \geq c_2 g(n) \geq 0 \hspace{1em} \forall n \geq n_0, \hspace{1em} c_1, c_2, n_0 \geq 0\\)
- O-notation: provides a non-necessarily asymptotically tight upper bound; so that \(c g(n) \geq f(n) \geq 0 \hspace{1em} \forall n \geq n_0, \hspace{1em} c, n_0 \geq 0\\)
- \(\Omega\\)-notation: provides a non-necessarily asymptotically tight lower bound; so that \(c g(n) \leq f(n) \geq 0 \hspace{1em} \forall n \geq n_0, \hspace{1em} c, n_0 \geq 0\\)
- o-notation: similar to O-notation, providing a non-asymptotically tight upper bound
- \(\omega\\)-notation: similar to \(\Omega\\)-notation, providing a non-asymptotically tight lower bound
The Big-O cheat sheet provides a useful reference to check best, average and worst cases for time complexity and worst case for space complexity, based on common algorithms.
\(\theta\\)-notation
This notation has been already used to define the rate of growth for an algorithm, based on its running time.
O-notation
Also called “Big-O”. Commonly used to define the worst-case running time. Some basics about Big-O can complement with examples.
\(\Omega\\)-notation
Commonly used to define the best-case running time; formalised by its lower bound.
Complexity analysis
Identifying the running time(s) of an algorithm can be done by looking at its behaviour (number of iterations, conditions on loops, specifics of the algorithm, etc) and computing its rate of growth; or by detailedly evaluating each step. The following examples aim to perform the latter procedure.
The following analysis will target a simple, iterative algorithm. For the recursive example, check the second part.
Selection sort
The selection sort is an inefficient sorting in-place algorithm. It works by iterating each time from a position \(i\\) to \(n\\) in an array \(A[1 \hspace{.2em} .. \hspace{.2em} n]\\), finding the minimum element contained at \(A[i+1 \hspace{.2em} .. \hspace{.2em} n]\\) and exchanging it with \(A[i]\\).
The “Introduction to Algorithms, 3rd edition” book provides exercise 2.2-2, asking for the analysis of the running time in best and worst case for such algorithm. The answer is based on the analysis provided on the same book for insertion-sort (check here for information on conditional steps).
A Python3 implementation would be as follows:
def swap(A: list, x: int, y: int) -> list:
aux = A[x]
A[x] = A[y]
A[y] = aux
return A
def insertion_sort(A: list) -> list:
for i in range(len(A)):
min = i
for j in range(i+1, len(A)):
if A[j] < A[min]:
min = j
if A[i] != A[min]:
A = swap(A, i, min)
return A
The pseudo-code can be used to analyse the running time in both worst and best cases:
SELECTION-SORT(A)
for i=1 to A.length-1
min = A[i]
for j=i+1 to A.length-1
if A[j] < min
min = A[j]
if A[i] != min
swap(min, A[i])
| Line | Instruction | Cost | Times | Explanation |
|---|---|---|---|---|
| 2 | for i=1 to A.length-1 |
\(c_1\\) | \(n+1\\) | 1 iteration per item in the outer loop + last 1 to get out of it |
| 3 | min = A[i] |
\(c_2\\) | \(n\\) | Runs every time in the outer loop |
| 4 | for j=i+1 to A.length-1 |
\(c_3\\) | \(\sum_{j=i+1}^{n} t_j\\) | Subset of items in the outer loop + last 1 to get out of inner loop |
| 5 | if A[j] < min |
\(c_4\\) | \(\sum_{j=i+1}^{n} (t_j-1)\\) | Worst-case: 1 iteration per item in the inner loop |
| 6 | min = A[j] |
\(c_5\\) | Same as L5 | Same as L5 |
| 7 | if A[i] != min |
\(c_6\\) | \(n\\) | Worst-case: 1 iteration per item in the outer loop |
| 8 | swap(min, A[i]) |
\(c_7\\) | Same as L7 | Same as L7 |
The worst-case scenario assumes the input array is not sorted or pseudo-random. The algorithm would perform all steps.
\[T(n) = c_1(n+1) + c_2n + c3\sum_{j=i+1}^{n} t_j + (c_4 + c_5)\sum_{j=i+1}^{n} (t_j-1) + (c_6 + c_7)n \\ = c_1 + (c_1 + c_2 + c_6 + c_7)n + c3\sum_{j=i+1}^{n} t_j + (c_4 + c_5)\sum_{j=i+1}^{n} (t_j-1) \\ = c_1 + (c_1 + c_2 + c_6 + c_7)n + c3\frac{n(n+1)}{2}-i + (c_4 + c_5)\frac{n(n-i)}{2} \\ = n + n^2 + n + n^2 - n = 2n^2 + n \\ \implies O(n^2)\]The best-case scenario assumes the input array is already sorted. The algorithm would still run both loops and conditional checks, yet it should not enter the latter.
\[T(n) = c_1(n+1) + c_2n + c3\sum_{j=i+1}^{n} t_j + c_4\sum_{j=i+1}^{n} (t_j-1) + c_6n \\ = c_1 + (c_1 + c_2 + c_6)n + c3\sum_{j=i+1}^{n} t_j + c_4\sum_{j=i+1}^{n} (t_j-1) \\ = c_1 + (c_1 + c_2 + c_6)n + c3\frac{n(n+1)}{2}-i + c_4\frac{n(n-i)}{2} \\ = n + c3\frac{n(n+1)}{2}-i + c_4\frac{n(n-i)}{2} \\ = n + n^2 + n + n^2 - n = 2n^2 + n \\ \implies \Omega(n^2)\]Note that the constants \(c_i\\), numeric constants and variables can be ignored to simplify the equation; as these do not lead the running time. Also, the summations have been replaced using the formula to sum elements in an arithmetic progression:
\[\sum_{j=i+1}^{n} j = \frac{n(n+1)}{2}-i \\ \sum_{j=i+1}^{n} (j-1) = \frac{n(n-i)}{2}\]The running time is quadratic in both cases. Even if some instructions are skipped in the best-case scenario, the cost-related constants are negligible when compared to the order of the terms formalising the iterations.
