It would be helpful to spend some time discussing what we mean by the performance complexity of code before we jump into code examples in Python and discuss tools to measure and optimize performance.
The performance complexity of a routine or function is defined in terms of how they respond to changes in the input size typically in terms of the time spent in executing the code.
This is usually represented by the so-called Big-O notation which belongs to a family of notations called the Bachmann–Landau notation or asymptotic notation.
The letter O is used as the rate of growth of a function with respect to input size—also called the order of the function.
Commonly used Big-O notations or function orders are shown in the following table in order of increasing complexity:
|
# |
Order |
Complexity |
Example |
|---|---|---|---|
|
1 |
O(1) |
Constant |
Looking for a key in a constant lookup table such as a HashMap or dictionary in Python |
|
2 |
O(log (n)) |
Logarithmic |
Searching for an item in a sorted array with a binary search. All operations on a heapq in Python |
|
3 |
O(n) |
Linear |
Searching an item in an array (list in Python) by traversing it |
|
4 |
O(n*k) |
Linear |
Worst-case complexity of Radix sort |
|
5 |
O(n * log (n)) |
n log-star n |
Worst-case complexity in a mergesort or heapsort algorithm |
|
6 |
O(n2) |
Quadratic |
Simple sorting algorithms such as bubblesort, insertion sort, and selection sort. Worst-case complexity on some sorting algorithms such as quicksort, shellsort, and so on |
|
7 |
O(2n) |
Exponential |
Trying to break a password of size n using brute force, solving the travelling salesman problem using dynamic programming |
|
8 |
O(n!) |
Factorial |
Generating all partitions of a set |
Table 1: Common Big-O notations for function orders with respect to input size "n"
When implementing a routine or algorithm accepting an input of a certain size n, the programmer ideally should aim for implementing it in an order that falls in the first five. Anything which is of the order of O(n) or O(n* log(n)) or lesser indicates reasonable to good performance.
Algorithms with an order of O(n2) can usually be optimized to work at a lower order. We will see some examples of this in the sections in the following diagram.
The following diagram shows how each of these orders grow with respect to n:
Graph of growth rate of each order of complexity (y axis) w.r.t input size (x axis)