What is the rankings for the big O notation for time complexity ? (with the highest rank being the fastest)
O(1) - Constant
O(log n) - Logarithmic
O(n) - Linear
O(n log n) - Linearithmic
O( n^2) - Polynomial
O(2^n) - Exponential
State the purpose of Big O notation
- Evaluate the complexity of an algorithm
- Show how the time / memory / resources increase as the data size increases
- Evaluate worst case scenario for an algorithm
Explain what is meant by Time Complexity
How the times scales as data size increases
Explain what is meant by Space Complexity
How much memory the algorithm needs as the data size increases
Explain O(1)
Always executes in the same amount of time regardless of the size of the data set
Explain O(log n)
Halves the data set in each pass
Explain O(n)
As the number of items in data set increase, the time it takes to complete the action increases by same amount
Explain O(n^2)
Performance is proportional to the square of the size of dataset. Reduces efficiency with larger datasets.
Explain O(2^n)
Doubles the dataset when an item is added to the dataset
What are the best, average, worst case time complexities for linear search
- Best = O(1)
- Average = O(n)
- Worst = O(n)
What are the best, average, worst case time complexities for binary search
- Best = O(1)
- Average = O(log n)
- Worst = O(log n)
What are the best, average, worst case time complexities for binary search tree
- Best = O(1)
- Average = O(log n)
- Worst = O(n)
What are the best, average, worst case time complexities for hashing
- Best = O(1)
- Average = O(1)
- Worst = O(n)
What are the best, average, worst case time complexities for bubble sort
- Best = O(n)
- Average = O(n^2)
- Worst = O(n^2)
What are the best, average, worst case time complexities for insertion sort
- Best = O(n)
- Average = O(n^2)
- Worst = O(n^2)
What are the best, average, worst case time complexities for merge sort
- Best = O(n log n)
- Average = O(n log n)
- Worst = O(n log n)
What are the best, average, worst case time complexities for quick sort
- Best = O(n log n)
- Average = O(n log n)
- Worst = O(n^2)
What are the space complexities for the SORTING ALGORITHMS
- Bubble Sort = O(1)
- Insertion Sort = O(1)
- Merge Sort = O(n)
- Quick Sort = O(log n)
