As I’ve been exploring algorithms more and more, time complexity is a concept that has come up more than a few times. Since my knowledge on the matter was sparse at best, I decided to do some investigating. After doing some research, I thought it would be helpful to share an easy and simple explanation for a few of the Big O speeds that we run into most frequently.
Before we get into speeds, lets do a quick explanation of what is Big O Notation and time complexity. Accoring to its Wikipedia page, Big O Notation is “a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.” Essentially, Big O indicates growth rates for functions, based on the input. These notations help us determine the speed in which an algorithm can achieve its desired outcome. The graph above shows some of the different time complexity cases, and how dramatically the times change based on input. We will be discussing four of these complexities: O(1), O(log n), O(n), and O(n²).
O(1) — Constant Time
This time is the same no matter what, regardless of the input size. An example of this is a function that does any basic task, like printing a string to the console. No matter the size, this step only takes one action.
O(n) — Linear Time
This time is proportional to the size of the input. If n is an array and we want to print each item, the time it takes to print each item depends on the size of the array.
O(n log) — Logarithmic Time
This time is a logarithm of the input, or repeated division. When something grows logarithmically, it is being divided. This is the opposite of exponetial growth (3² = 9 vs log3(9) = 2). Therefore the bigger the input, then the smaller the proportion of the input your program has to handle. An example of a logarithmic algorithm is a binary search.
O(n²) — Quadratic Time
As the size of the input increases, the time it takes for the algorithm to complete grows quadratically. A classic example of this is when a program uses a nested loop. In the earlier example about printing items from the array, if the size of the array is 10 times, and each item is printed 10 times, then that means the task of printing the item was 10x10 or 10².
Thats a basic explanation of Big O and some time complexities, I hope this was helpful.
