Big O Flashcards
What does time complexity describe?
The amount of computational time an algorithm takes
What is the focus of Big-O notation?
Worst-case scenarios
List the order of functions from fast to slow in Big-O notation.
- O(1) Constant
- O(log(n)) Logarithmic
- O(logc(n)) Polylogarithmic
- O(n) Linear
- O(n log(n)) Linearithmic/Loglinear
- O(n²) Quadratic
- O(n² log(n))
- O(n³) Polynomial
- O(2ⁿ) Exponential
- O(n!) Factorial
What is O(1) in Big-O notation?
Constant
What is O(log(n)) in Big-O notation?
Logarithmic
What does O(n) represent in Big-O notation?
Linear
What does O(n log(n)) represent?
Linearithmic/Loglinear
What is the Big-O notation for a quadratic function?
O(n²)
What is the Big-O notation for exponential growth?
O(2ⁿ)
What is the Big-O notation for factorial growth?
O(n!)
What properties do we ignore in Big-O notation?
Coefficients and log bases
When adding functions, what Big-O notation do we take?
The slowest function’s Big-O
When multiplying functions, what do we take in Big-O notation?
The product of the functions’ Big-O
What is the average/typical Big-O for Bubble sort?
Θ(n²), O(n²)
What is the average/typical Big-O for Quick sort?
Θ(n log(n)), O(n²)
What is the average/typical Big-O for Merge sort?
Θ(n log(n)), O(n log(n))
What is the average/typical Big-O for Radix sort?
Θ(n), O(n)
True or False: A loop in a loop is O(n²).
True
True or False: A loop in a loop in a loop is O(n).
False
Fill in the blank: If the number of steps stays the same no matter how large, then it’s _______.
O(1)
Fill in the blank: If you go through a n long list linearly, then you’ll take at most _______.
O(n)
Fill in the blank: A pseudocode loop that divides n by 2 repeatedly is _______.
O(log n)
What does the notation f(x) ∈ O(g(x)) indicate?
f(x) is a collection of functions that grows at most as fast as g(x)
What is the Big-O performance for Algorithm 1?
O(n)
What is the Big-O performance for Algorithm 2?
O(n)
What is the Big-O performance for Algorithm 3?
O(n)
What is the Big-O performance for Algorithm 4?
O(n log n)
What is the Big-O performance for Algorithm 5?
O(log n)
