Big O is the language & metric to describe the efficency of an algorithm. It describes:
- ▪ time complexity: execution time &
- ▪ space complexity: the memory or disk space used.
Big O is important when dealing with algorithms that operate at scale. If your sorting an array of 5 elements, the algorithm you use will have no noticably effect on time or space. If your sorting an array of millions of elements, the algorithm will have a big impact.
Analysing an algorithm is always based on the worst-case scenario. Imagine an algorithm that searched an array for an element. The algorithm started from the beginning & moved towards the end. When analysing it, we would base our results as if the element was in the last position of the array. This would take the longest time, thus the worst case scenario.
An example of the notation is O(n). n representing the input size. Below are examples of algorithms of different complexity.
O(1) - Constant Time
An algorithm whose execution time is constant, regardless of input size. Example, a function that takes an array & returns the 1st element.
O(n) - Linear Time
An algorithm whose execution time increases linearly as the input size increases. Example, a function that takes an array & logs each element.
O(log n) - Logarithmic Time
An algorithm whose execution time increases in proportion to the logarithm of the input size. Time will barely increases as the input exponentially increases. Example, a binary search. When you see a problem where the number of elements in the problem space gets halved each time, that will likely be a O(log n) runtime.
O(n2) - Quadratic Time
An algorithm whose execution time is the squared size of the input. Example, a selection sort. Commonly, 2 nested loops indicates an algorithm is O(n2), O(n3) for 3 nested loops, O(n4) for 4 nested loops, ..
O(2n) - Exponential Time
An algorithm whose execution time doubles with each addition to the input. Example, calculating the Fibonacci sequence.
If we create an array of size n, it will require 0(n) space. If we create a 2-dimensional array of size n x n, it will require 0(n2) space. Call stack space in recursive calls counts too:
O(n) - Linear Space
Below, each call adds a frame to the stack, each requiring memory.
Drop Constant & Non-Dominant Terms
Big 0 describes the rate of increase. For this reason, we drop the constants in runtime. Example, an algorithm that iterates through an array twice. You could describe this as O(2n). However, we simplify it to O(n). We also drop non-dominate terms. O(n2 + n) becomes O(n2).