I started learning about Big O Notations recently and I’ve read many articles and watched helpful videos too.
Tried an example on the exponential runtime:
function addAndLog(array){
for ( var i = 0; i < array.length; i++ ) {
for(var j = 0; j < array.length; j++ ) {
console.log(array[i] + [j]);
}
}
}
addAndLog([ 'A', 'B', 'C']);
addAndLog([ 'A', 'B', 'C', 'D']);
addAndLog([ 'A', 'B', 'C', 'D', 'E']);
n^2 would be quadratic and 2^n would be exponential. To see the difference you can compare few n values:
n = 1;
n ** 2; // 1
2 ** n; // 2
n = 10;
n ** 2; // 100
2 ** n; // 1024
n = 1000;
n ** 2; // 1000000
2 ** n; // 1.0715086071862673e+301
The most famous example of exponential algorithm is permutations algorithm, aka password brute forcing. You can assume numbers in cryptography hashing algorithms as n, so SHA-256 password has 2 ^ 256 permutations (which no computer on Earth will be able to crack in universe lifetime)