Big O
No description yet. This curated deck is ready for daily study.
Card preview (24)
What is O(1) complexity called?
Constant time complexity
Give an example of O(1) complexity.
Accessing an array element by index
What is O(log n) complexity called?
Logarithmic time complexity
Give an example of O(log n) complexity.
Binary search
What is O(n) complexity called?
Linear time complexity
Give an example of O(n) complexity.
Linear search through a list
What is O(n log n) complexity called?
Linearithmic time complexity
Give an example of O(n log n) complexity.
Merge sort or quick sort (average case)
What is O(n²) complexity called?
Quadratic (a type of polynomial) time complexity
Give an example of O(n²) complexity.
Bubble sort or insertion sort in the worst case
What is O(2ⁿ) complexity called?
Exponential time complexity
Give an example of O(2ⁿ) complexity.
Naive recursive Fibonacci algorithm
Which Big O graph is flat, unaffected by input size?
O(1) Constant
Which Big O graph rises slowly and flattens?
O(log n) Logarithmic
Which Big O graph is a straight diagonal line?
O(n) Linear
Which Big O graph is steeper than linear but less than quadratic?
O(n log n) Linearithmic
Which Big O graph curves steeply upwards as n increases?
O(n²) Quadratic
Which Big O graph shoots up almost vertically?
O(2ⁿ) Exponential
Linear search best case complexity?
O(1)
Linear search average case complexity?
O(n)
Linear search worst case complexity?
O(n)
Binary search best case complexity?
O(1)
Binary search average case complexity?
O(log n)
Binary search worst case complexity?
O(log n)