Big-O
Big-O
Vocab
AlgorithmA set of rules and processes for solving a problemBig-O NotationA description of the worst-case performance of an algorithm
What is Big-O?
Big O notation is used in Computer Science to describe the performance or complexity of an algorithm. Big O specifically describes the worst-case scenario, and can be used to describe the execution time required or the space used (e.g. in memory or on disk) by an algorithm.
Big Ω (Omega) is the best performance.
Big Θ (Theta) is the average performance.
You can think about these as ratings for your algorithm. These ratings can communicate the amount of space and time you can expect your algorithm to need.
Factors in determining complexity
- Number of comparisons
- Amount of space used in memory
Big-O Cheatsheet
| 0( log n ) | 0( n ) | 0( n^2 ) | 0( 2^n )
------------------------------------------------------------
100 | 2 | 100 | 10,000 | 1.27E+30
------------------------------------------------------------
1000 | 3 | 1,000 | 1,000,000 | 1.07E+301
------------------------------------------------------------
10000 | 4 | 10,000 | 1.00E+08 | 1.07E+3010
------------------------------------------------------------
Big-O Examples
O(1)
var randomNumbers = [ 10, 2, 9, 15, 22 ];
function isFirstElementNumber(array) {
return typeof array[0] === 'number';
}
isFirstElementNumber(randomNumbers);
O(n)
var randomNumbers = [ 10, 2, 9, 15, 22 ];
function doesNumberExist (array, number) {
for (let i = 0; i < array.length; i++) {
if (array[i] === number) {
return true;
}
}
return false;
}
doesNumberExist(randomNumbers, 27);
O(n^2)
var randomNumbers = [ 10, 2, 9, 15, 22 ];
function containsDuplicates (array, number) {
for (let i = 0; i < array.length; i++) {
for (let j = 0; j < array.length; j++) {
if (i !== j && array[i] === array[j]) {
return true;
}
}
}
return false;
}
containsDuplicates(randomNumbers, 27);
O(2^n)
var randomNumbers = [ 10, 2, 9, 15, 22 ];
function fibonacci(number) {
if (number <= 1) {
return number;
}
return fibonacci(number - 2) + fibonacci(number - 1);
}
fibonacci(20)
