Big-O definition
- Algorithms course
- Beginner
- Lesson 6/80
- 4 min
Learn that Big-O is an upper bound with O(1), O(n), O(n^2) examples.
Big-O definition
Big-O notation describes the upper bound of an algorithm's worst-case runtime. O(n) is linear, O(n^2) is quadratic growth.
Big-O ignores constant factors and lower-order terms; it keeps only the fastest-growing term. For example 3n + 5 becomes O(n).
Common Big-O values
Most common Big-O values, fast to slow: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) merge sort, O(n^2) quadratic.
This order is a key guide when choosing the right algorithm for a task. On large inputs, lower Big-O always wins.
Practice First element
Write first_element(arr). Return the first element. Print 7 with print(first_element([7, 3, 9])).
Starter code
def first_element(arr):
# Return first elementSample solution
def first_element(arr):
# Return first element
return arr[0]
print(first_element([7, 3, 9]))Expected output
7
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Big-O upper bound
Big-O represents the ____ of the worst case.Big-O represents the upper bound of the worst case.Explanation: upper bound is right.
2 Big-O definition: match the terms
| Term | Meaning |
|---|---|
O(1) |
Constant |
O(n) |
Linear |
O(log n) |
Logarithmic |
O(n^2) |
Quadratic |
3 What does O(1) mean?
- Linear time
- Constant time Correct answer
- Quadratic time
- Logarithmic time
Explanation: O(1) is constant time.