Asymptotic Efficiency Flashcards
Class 1
Constant, running time doesn’t change based off input (simple equations)
Class log n
Logarithmic, typically occurs by cutting down a problem’s size by a constant factor iteratively (Binary search)
Class n
Linear, running time increases at the same rate as input (Linear search)
Class n log n
Linearithmic, occurs with many divide and conquer algorithms including average mergesort and quicksort (Mergesort, quicksort)
Class n^2
Quadratic, typically algorithms with 2 embedded loops
Class n^3
Cubic, typically algorithms with 3 embedded loops
Class 2^n
Exponential, typically for algorithms that generate all subsets of an n element set
Class n!
Factorial, typical for algorithms that generate all permutations of an n element set (Travelling salesman via brute force)
P class problem
All problems that can be solved with polynomial time complexity with respect to size of the input
NP class problem
All problems that cannot be determined or solved in polynomial time, however correct solutions can be verified in polynomial time given right information
NP-Complete
Subset of NP class where once one can be solvable in polynomial time, they can all be solved in polynomial time (Travelling Salesman decision problem)
NP-Hard
Can neither be solved or have possible solutions verified for correctness in polynomial time (Knapsack 0-1 optimisation problem)
Tractable
Problems that can be solved in polynomial time
O(1) tractable or intractable?
tractable
O(n) tractable or intractable?
tractable
