## OVERVIEW

Computer algorithm have changed dramatically for the past century and algorithm is a fundamental skills for most programmers who intend to develop a system that is scalable and performant.

Algorithm become really useful when dealing with large amounts of data or solving complex problems.

On top of that, algorithm are usually asked during job interviews. So, it’s better to be safe than be sorry.

## Big-O Notation

This is a mathematical model used to measure and classify algorithm. And it’s also known to estimate the **time efficiency** of running an algorithm as function of the input size. With the understanding of time efficiency of each algorithm, we able to determine how well our apps will work in terms of speed and performance.

There are several way to determine the time efficiency and they are divided into different categories.

**1. Constant Time – O(1) **

**This is the best.** With constant time, it describe an algorithm that will execute the same amount of time regardless of the size of input. In other word, the run time of algorithm is the same amount of time whether it operates on one or on several thousand or million entries. Example includes **looking up element of an array by its index **or **pushing & popping from Stack**.

1 2 3 |
let numbers = [1, 2, 3, 4, 5, 6] numbers[0] numbers[2] |

**2. Linear Time – O(n)**

**Good performance. **With linear time, it describes the algorithm in which the performance grow linearly and in direct proportion to the size of the input data set. In other word, the run of algorithm time complexity will increase at the same rate as the input dataset grows. For example, if it takes 1 second to run 1000 entries, it will take ten times to run 10,000 entries which is going to be 10 seconds. Example includes **sequential search**.

1 2 3 4 |
let numbers = [1, 2, 3, 4, 5] for i in 0...numbers.count{ print(numbers[i]) } |

**3. Quadratic Time – O(n^2)**

**Kinda slow. **With quadratic time, it describe the algorithm in which performance is directly proportional to the square of the size of the input data set. According to the graph above, we see that the runtime increases sharply, faster than the input sizes and this is due to the result of a nested operations on a dataset. For example, if it takes 100 milliseconds for 100 entries, then with 2000 entries, it will take about 40 seconds to run and with 4000 entries, it will take 26 minutes to run. You see the significance jump in the time run? Example includes **insertion sort**.

1 2 3 4 |
for i in 1...5 { for j in 1...i{ } } |

**4. Logarithmic Time – O(log n)**

**Pretty Great. **With logarithmic time, it is a highly efficient algorithm as it has shown its worth that while the data size goes up exponentially, the time goes up linearly. For example, if it takes 1 millisecond to compute 10 entries, it will take 2 milliseconds to computer 100 elements and 3 miliseconds to computer 1000 elements. Binary search, quick sort and divide and conquer type of algorithm usually run on logarithm time. Example includes **binary search**.

1 2 3 4 5 |
var j = 1 while j < n { // do constant time stuff j *= 2 } |