Big O notation
Big O notation is used to describe the time spent by an algorithm to run.
\(O(1)\) - Constant time
const x = 10
printf("Lorem ipsum")
\(O(log(n))\) - Log time
for(int i = 1; i <= n; i = i * 2)
print "hello";
Notice the post operation of the for loop multiples the current value of i by 2, so i
goes from 1 to 2 to 4 to 8 to 16 to 32…
for(double i = 1; i < n; i = i * 1.02)
print "hello";
As long as the number is greater than 1 and the result is repeatedly multiplied against itself (i = i * 1.02), that you are looking at a logarithmic algorithm.
\(O(n)\) Linear time
for(int i = 0; i < n; i++)
print "hello";
\(O(n*log(n))\) nlog(n)
Think of this as a combination of O(log(n))
and O(n)
. The nesting of the for loops help us obtain the O(n*log(n))
for(int i = 0; i < n; i++)
for(int j = 1; j < n; j = j * 2)
print "hello";
\(O(n^2)\) - n squared
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
print "hello";
Is obtained easily by nesting standard for loops.
\(O(2^n)\) - exponential time example
When the algorithm specifies a growth rate that doubles every time the input data set is added.
const recursiveFibonacci = (n) => {
if (n < 2) {
return n;
}
return recursiveFibonacci(n - 1) + recursiveFibonacci(n - 2);
};
console.log(recursiveFibonacci(6)); // 8
\(O(n!)\) - factorial time
For example, the factorial of 5, or 5!, is:
5 * 4 * 3 * 2 * 1 = 120
We will find ourselves writing algorithms with factorial time complexity when calculating permutations and combinations.
Those are basically NP problems (Nondeterministic Polynomial).