Big-O notation
The Big-O notation is a notation used to talk about the long-term growth rates of functions. It is often used for algorithms analysis, to talk about the execution of an algorithm or related concepts such as the complexity of space.
O(1) — Constant execution time:
An algorithm is of O(1) complexity if it requires constant execution time. The execution time is the same regardless of the size of the input values. Who says constancy also Says O(1).
O(log n) — Logarithmic execution time:
Simply a logarithmic trend is the opposite of an exponential trend. Where an exponential trend will multiply over time, the logarithmic trend will divide.
O(n) — Linear execution tim:
We say of an algorithm that it is of complexity O(n) if, during its execution, it requires it to go through each input element.
O(n log (n)) linear complexity:
uses the same approach as logarithmic complexity, except it does so on each element of input n.
O(n²) — Quadratic/Squared execution time:
An algorithm whose execution time is directly proportional to the square of the input data set size is said to be of O(n²) complexity.
O(k^n) — Exponential execution time:
An algorithm whose execution time is growing exponentially is growing k times for every increase of n.
Clearly, the shorter the execution time, the more efficient an algorithm.
Also, we use this notation for space complexity to determine the necessity of extra memory.
Suppose an algorithm requires no extra or a fixed number of additional memory, not depending on the size of the input values. In that case, it will be O(1) in space complexity.
Suppose an algorithm requires the same quantity of extra memory of the input values. In that case, it will be O(n) in space complexity.
And so on.
