Big O Notation Flashcards
What does Big O Notation Mean
The upper limit of the amount of time it takes to solve a particular problem
What is constant time complexity?
O(1), the amount of time it takes to solve a problem is unrelated to the amount inputted.
What is linear time complexity?
O(n), the amount of time taken to solve a problem is directly proportional to the amount inputted.
What is polynomial time complexity?
O(n^x), the amount of time it takes to solve a problem is directly proportional the amount inputted to the power of another number
What is logarithmic time complexity?
O(log(N)), the amount of time taken to solve a problem will increase at a smaller rate as the number of elements inputted.
What is polynomial time complexity?
O(2^X)
The amount of time taken to complete an algorithm will double with every turn.
Complexity for algorithms
Linear: O(n)
Binary: O(log(n))
Qucik sort: O(n^2)
Merge Sort: O(log(N)
Bubble and insertion: O(n^2)
Dijkastras Algorithm Tip
Find the shortest distance from the start that has not yet been visited
A* Algorithm Tip
Like Dijkastras Algorithm except add the heuristic
