Algorithmic complexity Flashcards
Define time complexity
time it takes for a program to run
Define space complexity
memory that is required
Define Big O Notation
allows us to compare one algorithm to another as to choose the best option
How to calculate Big O
-take the highest power
e.g.
3n^3 + 4n^2
O(n^3)
What is the Big O for constant time complexity
O(1)
What is Big O for linear search
O(n)
What is Big O for binary search
O(logn)
What is Big O for Binary tree search
O(logn)
What is Big O for Bubble sort
O(n^2)
What is Big O for Merge sort
O(nlogn)
What is the order of complexities?
- Constant
- Logarithmic
- Linear
- Polynomial
- Exponential
- Factorial
‘Complexities love licking p*nises, especially Flynn’s’
Define intractable
it is too complex to be solved in polynomial time, heuristic methods can be used to find a ‘good enough’ solution
(DIFFERENT TO UNSOLVABLE)
Define heuristic method
practical methods to find a sufficient, but not optimal solution
Define halting problem
- used by Alan Turing as proof that some problems are unsolvable for a computer
- tell if program will halt without running it
What is Big O for Travelling salesman
O(n!)
