# Big O Notation

## Vocab

• `Algorithm` A set of rules and processes for solving a problem
• `Big-O Notation` A 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 === '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)
``````

Function Performance

## Lesson Search Results

### Showing top 10 results 