Big O Notation

This is a notation which is commonly used to express the time or space complexity of an operation. In other words, how quickly the time/space required for the operation grows.

It does not necessarily indicate how long (or how much space) the operation will actually take. For example, an operation that always takes 100 seconds is O(1), and an operation that starts at 0.0001 seconds and grows by 0.0001 seconds each time is O(n). But it would be better to use the latter unless you're going to need it more than a million times.

Common

• O(1): Constant time. The operation always takes the same amount of time/space.
• O(log(n)): Logarithmic time. The time/space required increases with the amount of data provided, but by a half-step for each additional element. For example, binary search.
• O(n): Linear time. The time/space required grows by the same amount each time.
• O(n + 1): Linear time plus one. This type of growth is problematic and often encountered in ORMs, where only one query should be issued to retrieve the data.
• O(x + y): Linear time for two independent variables. For example, if we have to traverse the length of two arrays once each.
• O(xy): If we have to nest one loop inside the other.
• O(n²): Quadratic time.
• O(2^n):
• O(n^n):