=====Time Complexity======
There are different measurements of the speed of any given algorithm. Given an
input size of N, they can be described as follows:
^Name^Speed^Description^Formula^Example^
|factorial time|slower|takes an amount of time proportional to the factorial of N| N! |Brute force solution to Traveling Salesman Problem|
|exponential time|slow|takes an amount of time proportional to a constant raised to the Nth power| KN |Brute force solution to Rubik's Cube|
|polynomial time|fast|takes an amount of time proportional to N raised to some constant power| NK |Comparison sorts (bubble, insertion, selection sort)|
|linearithmic time|faster|takes an amount of time between linear and polynomial| N * log(N) |The Linear logarithmic sorts (quicksort, heapsort, mergesort)|
|linear time|even faster|takes an amount of time directly proportional to N| K * N |Iterating through an array|
|logarithmic time|much faster|takes an amount of time proportional to the logarithm of N| K * log(N) |Binary Search|
|constant time|fastest|takes a fixed amount of time, no matter how large the input is| K |Array index lookup|
====Complexity Analysis====
A given operation can have different time complexities with different orders/sets of input. The different methods of time complexity analysis are as follows:
^Name^Description^Example^
|best-case|A case where the operation executes as fast as it possibly can| Bubblesort has a best-case time complexity of N.|
|average-case|A case where the operation executes in a time comparable to the majority of possible cases| Quicksort has an average-case time complexity of N * log(N)|
|worst-case|A case where the operation executes as slowly as it possibly can| Quicksort has a worst-case time complexity of N2|
|amortized worst-case|The average worst-case taken over an infinite number of inputs| vector::push_back() has an amortized worst-case time complexity of K (constant time)|
Choosing the right algorithm depends upon which cases you expect your application to encounter.