Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.  // by Wikipedia

## Big Os

• O(1) –> Constant- no loops
• O(n) –>Linear- for loops, while loops through n items
• O(log N) –> Logarithmic- usually searching algorithms have log n if they are sorted (Binary Search)
• O(n log(n)) –> Log Linear- usually sorting operations
• O(n^2) –> Quadratic- every element in a collection needs to be compared to ever other element. Two nested loops
• O(2^n) –> Exponential- recursive algorithms that solves a problem of size N
• O(n!) –> Factorial- you are adding a loop for every element

*Iterating through half a collection is still O(n)

*Two separate collections: O(a * b)

## What can cause time in a function?

• Operations (+, -, *, /)
• Comparisons (<, >, ==)
• Looping (for, while)
• Outside Function call (function())

## Rule Book

• Rule 1: Always worst Case
–> even there is a “break” condition inside the for loop, think the worst case that the beak point is the last item in the loop
• Rule 2: Remove Constants
• Rule 3: Different inputs should have different variables. O(a+b). A and B arrays nested would be O(a*b)
+ for steps in order
* for nested steps
• Rule 4: Drop Non-dominant terms

## What causes Space complexity

• Variables
• Data Structures
• Function Call
• Allocations

## Examples

#### example1

``````// What is the Big O of the below function? (Hint, you may want to go line by line)
function funChallenge(input) {
let a = 10; //O(1)
a = 50 + 3; //O(1)

for (let i = 0; i < input.length; i++) { //O(n)
anotherFunction(); //O(n)
let stranger = true; //O(n)
a++; //O(n)
}
return a; //O(1)
}``````

A: O (n) –> big O (3+4n)

#### example2

``````// What is the Big O of the below function? (Hint, you may want to go line by line)
function anotherFunChallenge(input) {
let a = 5; //O(1)
let b = 10;//O(1)
let c = 50;//O(1)
for (let i = 0; i < input; i++) {
let x = i + 1;//O(n)
let y = i + 2;//O(n)
let z = i + 3;//O(n)
}
for (let j = 0; j < input; j++) {
let p = j * 2;//O(n)
let q = j * 2;//O(n)
}
let whoAmI = "I don't know";//O(1)
}``````

A: Still O (n) –> by rule 2, ignore the Constants part.

#### example3

``````function printFirstItemThenFirstHalfThenSayHi100Times(items) {
console.log(items);

var middleIndex = Math.floor(items.length / 2);
var index = 0;

while (index < middleIndex) {
console.log(items[index]);
index++;
}

for (var i = 0; i < 100; i++) {
console.log('hi');
}
}``````

A: Still O (n) // O (1+n/2 + 100) –> ignore the constants part, and Iterating through half a collection is still O(n)

#### example4

``````const boxes = ['a', 'b', 'c', 'd', 'e'];
function logAllPairsOfArray(array) {
for (let i = 0; i < array.length; i++) {
for (let j = 0; j < array.length; j++) {
console.log(array[i], array[j])
}
}
}

logAllPairsOfArray(boxes)``````

A: O ( n ^ 2 ) –> nested loop

#### example5

``````function printAllNumbersThenAllPairSums(numbers) {

console.log('these are the numbers:');
numbers.forEach(function(number) {
console.log(number);
});

console.log('and these are their sums:');
numbers.forEach(function(firstNumber) {
numbers.forEach(function(secondNumber) {
console.log(firstNumber + secondNumber);
});
});
}

printAllNumbersThenAllPairSums([1,2,3,4,5])``````

A: O (n^2) –> originally should be O (n+n^2), but by rule 4, we keep the dominant part only on the big scale.

#### example5

``'sdfhasdklfjas;dlkfjasd;lkfj'.length // O(1)``

The answer to this example actually depends on the language you are using. In JS, “.length” is not looping each letter of the string, so the answer is O (1).

## Conclusion

What is a good code? –> Readable and Scalable (speed and Memory) … Higher Speed would take more memory and low usage of memory would result in slow speed. We always need to trade-off, save time or save space.

Knowing how much time your code takes how much memory it uses is very very critical. Those are expensive things for a company or a product. Now big-O is a very important concept that you won’t find in your day-to-day job but it’s something that should always be in the back of your mind and good developers and engineers always have this knowledge. That is why it is such a popular topic during interviews.

Other resources:

What is the difference between big oh, big omega and big theta notations?

Big-O cheat sheet