Comparing complexities
- Algorithms course
- Beginner
- Lesson 7/80
- 4 min
Order O(1), O(log n), O(n), O(n log n), O(n^2) from fast to slow.
Comparing complexities
Big-O values from fast to slow: O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n). O(1) is fastest.
O(1) runs in constant time regardless of input. O(n^2) quadruples when input doubles.
Worst and best case
An algorithm's worst case is the longest-running input; its best case is the shortest-running input.
In linear search, if the target is first the best case is O(1); if last, the worst case is O(n). Big-O usually denotes the worst case.
Practice Array length
Write count_items(arr). Count elements with for and return. Print 3 with print(count_items([4, 5, 6])).
Starter code
def count_items(arr):
# Count itemsSample solution
def count_items(arr):
# Count items
count = 0
for x in arr:
count = count + 1
return count
print(count_items([4, 5, 6]))Expected output
3
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Comparing complexities: match the terms
| Term | Meaning |
|---|---|
O(1) |
Constant |
O(n) |
Linear |
O(n^2) |
Quadratic |
O(log n) |
Logarithmic |
2 Which is the slowest growth?
- O(1)
- O(log n)
- O(n^2) Correct answer
- O(n)
Explanation: O(n^2) is the slowest growth.
3 Worst case
Big-O usually denotes the ____ case.Big-O usually denotes the worst case.Explanation: worst is right.