**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

Contents

## 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[0]);
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?