Performance complexity
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 look-up table such as a HashMap or dictionary in Python |
|
2 |
O(log (n)) |
Logarithmic |
Searching for an item in a sorted... |
