# Algorithms

So there are different types of algorithms and different times to choose each. The common answer is to say “my language implements this already, all I have to do is something like `myArr.sort()`

or `myArr.indexOf(x)`

”. So why learn things that are already implemented in your toolset of choice?

The truth is, algorithms are one of the fundamentals of computer science, and as such they shape the way you think about problems before they even come up. Sure you can call `myArr.sort()`

on a collection of items when they present themself in a well structured set of data, but knowing how a sort works fundamentally will help you better structure your data in the first place.

## Examples

### Search

**Binary Search** *Good first choice. Simple to write and intuitive to understand*

### Sort

**Insertion Sort** *Good first choice. Simple to write and intuitive to understand*

## Keywords and Terms

### Characteristics

- online/offline
- online: can sort a list as it receives it
- offline: needs all the data upfront

- stable: doesn’t change the relative order of elements with equal keys
- in-place: only requires a constant amount of additional memory space O(1)

### Algorithmic Complexity

- Constant: O(1)
- doesn’t matter the size of the input, will always take the same amount of time

- Linear: O(n)
- complexity increases linearly with the number of items given <!– for (int i = 0; i < N; i++) {

} –> - Quadratic: O(n^2) - Logarithmic: O(Log n) - inverse operation of exponentiation - Linearithmic: O(n log n)

### Types

- divide and conquer algorithm
- three steps
- divide the problem into sub-problems
- recursively solve the sub-problems
- combine the answers of the sub-problems

- three steps
- greedy algorithm
- build up a solution piece-by-piece, always choosing the next piece that provides the most obvious/immediate benefit
- usually more efficient than other techniques
- not always able to be applied

- dynamic programming
- breaks a hard problem into smaller sub-problems, and stores their results to avoid re-computing the answer to all those solutions as the larger problem is eventually solved
- two main properties
- overlapping sub-problems
- optimal sub-structure
- i.e. can the optimal solution of the main problem be solved be obtained from using the optimal solution of it’s sub-problems?