Summary - Big-O
- Algorithms course
- Beginner
- Lesson 8/80
- 4 min
Practice Big-O with a mini task computing a function's growth rate.
Summary - Big-O
In this group you learned time complexity, Big-O notation and common growth rates. Big-O gives the worst-case upper bound.
O(1) is fastest, O(n^2) is slow. On large inputs, lower Big-O always wins.
Practice Find max
Write find_max(arr). Find the largest with a for loop and return. Print 9 with print(find_max([3, 7, 2, 9, 5])).
Starter code
def find_max(arr):
# Find maxSample solution
def find_max(arr):
# Find max
max_val = arr[0]
for x in arr:
if x > max_val:
max_val = x
return max_val
print(find_max([3, 7, 2, 9, 5]))Expected output
9
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Summary - Big-O: match the terms
| Term | Meaning |
|---|---|
O(1) |
Constant |
O(n) |
Linear |
O(log n) |
Logarithmic |
O(n^2) |
Quadratic |
2 Big-O notation
Question
Big-O represents the ____ of the worst case.
Answer
Big-O represents the upper bound of the worst case.Explanation: upper bound is right.
3 Which is an O(n) algorithm?
- Binary search
- Array access
- Bubble sort
- Linear search Correct answer
Explanation: Linear search is O(n).