Big O notation is the language we use to determine and communicate how long an algorithm takes to run, expressed in terms of how quickly it grows relative to input (n) as the input gets arbitrarily large, with the purpose of comparing the efficiency of different approaches.
Because it is difficult to pin down the exact runtime of an algorithm (this depends on the speed of the processor, what else the computer is running, and other factors) we use big O notation to talk about how quickly runtime grows, relative to the size of the input (n).
Big O analysis is an asymptotic analysis. In Big O analysis, we care the most about the parts that grow the fastest as the input grows. Another way to say this is that Big O is concerned with the worst case/ slowest scenario.
What problems does Big O solve?
It helps us answer “will it scale?”. It also gives us a shared language to discuss performance with developers and mathematicians.
Some specific examples :
Constant Time/Constant Complexity O(1)
A method that requires just one step runs in constant time or O(1) time relative to its input. The input array could be 1 or 1,00 but the method still runs in one step. An example of this is a function that prints the same thing, the number of times indicated.
Logarithmic Time/Logarithmic Complexity O(log n)
The number of computations is increased by the log of the input value.
Linear Time O(n)
An example of a function with O(n) runtime is a function that prints the item for each item in an array of items. N is the number of items in the array.
Quadratic Time O (n²)
An example of this is a method with two nested loops. If our array has n items, our outer loop runs n times for each iteration of the outer loop, resulting in a total of n².
A note on N
Sometimes n is the actual number that is the input to a method and other times n is the number of items in an input array/map/object.
Drop Constants and Less Significant Terms
Constants and less significant terms can be dropped when calculating big O notation. O(2n) is the same as O(n). This is because we are looking for what happens as n gets arbitrarily large. This means that adding by 100 or dividing by 2 would have a decreasingly significant effect. For these purposes, O( n + n²) is just O (n²).
Worst case vs Best case
If the worst case is O(n) and the best case is O(1) you can say run time O(n) since the worst-case language is implied when talking about Big O.
