BigO Notation Flashcards
Best scenario for linear search
O(1) - constant
Average scenario for linear search
O(n) - linear
Worst scenario for linear search
O(n) - linear
Best scenario for binary search
O(1) - constant
Average scenario for binary search
O(log n) - logarithmic
Worst scenario for binary search
O(log n) - logarithmic
Best scenario (time) for bubble sort
O(n) - linear
Average scenario (time) for bubble sort
O(n^2) - polynomial
Worst scenario (time) for bubble sort
O(n^2) - polynomial
Space complexity for bubble sort
O(1) - constant
Best scenario (time) for insertion sort
O(n) - linear
Average scenario (time) for insertion sort
O(n^2) - polynomial
Worst scenario (time) for insertion sort
O(n^2) - polynomial
Space complexity for insertion sort
O(1) - constant
Best scenario (time) for merge sort
O(n log n) - linearithmic
Average scenario (time) for merge sort
O(n log n) - linearithmic
Worst scenario (time) for merge sort
O(n log n) - linearithmic
Space complexity for merge sort
O(n) - linear
Best scenario (time) for quick sort
O(n log n) - linearithmic
Average scenario (time) for quick sort
O(n log n) - linaerithmic
Worst scenario (time) for quick sort
O(n^2) - polynomial
Space complexity for quick sort
O(log n) - logarithmic
Order of bigO
CLoLiLinPolE (Constant, Logarithmic, Linear, Linearithmic, Polynomial, Exponential)
Explain the bigO notation O(1)
Constant complexity. Executes in the same amount of time regardless of data set.
Explain the bigO notation O(log n)
Logarithmic complexity. Halves the data set in each pass. Efficient with large data sets. The algorithm will take one additional step each time the data (n) doubles. Log n is the inverse of exponential E.g. Binary Search
Explain the bigO notation O(n)
Linear complexity. Performance is proportional to the size of the data set and increases as the data set grows. E.g. Linear Search
Explain the bigO notation O(n log n)
Linearithmic. Algorithms that divide a data set but can be solved using concurrency on independent divided lists. E.g. Merge Sort
Explain the bigO notation O(n^2)
Polynomial complexity. Performance is proportional to the square of the size of the data set. Efficiency is reduced with large data sets. E.g. Bubble Sort, Insertion Sort
Explain the bigO notation O(2^n)
Exponential complexity. Doubles with each addition to the data set in each pass
explain bigO - 3 marks
Big O defines the runtime required to execute an algorithm by identifying how the performance of your algorithm will change as the input size grows
Big O = how the algorithm scales with larger data sets
Evaluates the complexity of the algorithm (1)
Shows how the time / memory / resources increase as the data size increases (1)
Evaluates worst case scenario for the algorithm (1)
