# Algorithms

## Introduction
If you choose the right data structure, the algorithm will be self-evident
Data structure dictates which algorithms you can apply

## Functions
### Mathematics
Set of X to a set of Y assigns each element of X exactly one element of Y
Functions don't have side effects and only depend on their input
f(x) = 42 (constant)
f(x) = 2x (linear)
f(x) = x^2 (quadratic)
f(x) = x^3 (cubic)
f(x) = log2(x) (logarithmic)
f(x) = 2^x (exponential)
f(x) = x! (factorial)

Factorial is recursive
N! = (N - 1)! * N for all N > 0

### Complexity
Constant < log(n) < √n < n < n^2 < 2^n

### Logarithms
The inverse of exponentiation

If Y is product of B to the power of P ( B^P )
Y = B^P, therefore
P = logB(Y)

### Big O notation
Express time or space complexity (asymptotic complexity). Rough approximation of number of operations needed to execute.
Time relative to number of elements. Descrbines which function best describes its growth. Big O is always a function or combination of functions where n is the number of elements.

f(n) = O(g(n)) means there are positive constants: c and k
0 <= f(n) <= cg(n) for all n >= k

### Constant time operations O(1)
Does not depend on number of elements
Examples:
- Adding element to end of linked list
- Accessing array by index
- Accessing root of tree
- Accessing/adding element to good hash table

### Logarithmic Operations O(log(n))
Not much worse than constant time
Divide to conquer
Base is not relevant (especially as we approach infinity), but usually 2
Examples:
- binary search sorted array
- Add/search balanced BST

### Linear Operations O(n)
- Traverse a list or array
- Add N elements to vector/list/table
- Search/Insert/Remove element to arbitrary position in list/array
  - Must be traversed (average => n / 2, but treat it as n)

### n log(n)
Examples:
- Insert N elements in balanced BST (N times log(n))
- Merge/Heal sort
- Quick sort (worst case O(n^2))

### Quadratic Operations O(n^2)
Avoid for large data sets because number of operations grows quickly
- Nested loops
- Insert into unbalanced BST
- Bubble sort
- Insertion sort

### Cubic Operations O(n^3)
- Multiplication of [n x n] matrices

### Exponential Operations O(2^n)
- Traveling salesman with dynamically programmed solution

### Factorial Operations O(n!)
- Don't even try it