O(1) and O(n)
Big-O: lesson 2 of 5
One step, or every step? That's the whole difference.
Lesson 2 of 5 · 4 min
O(1) and O(n)
Step 1 of 11
O(1) ops0O(n) ops0
nums[0] · O(1)
k
7
3
9
1
8
5
6
42
contains(42) · O(n)
s
7
3
9
1
8
5
6
42
Same list, two jobs: read one slot, or look for a value that could be anywhere.
The Idea
O(1) means the work never changes, no matter how large the input gets. O(n) means you touch every item once. Telling these two apart in your own code is the fastest complexity skill to pick up.
Real-World Example
A vending machine is O(1): press B4 and the snack drops, whether the machine holds ten items or two hundred. Hunting for one brand down every supermarket aisle is O(n), so a bigger store means a longer walk.
The Code
def first_item(nums):
# one lookup, same cost for any list size -> O(1)
return nums[0]
def contains(nums, target):
# may scan every element -> O(n)
for x in nums:
if x == target:
return True
return FalseYour turn
Put the steps in the right order.
- Compare the current item to the target
- Start at the first element
- Return False after the whole scan finds nothing
- Move to the next element if there is no match
Mini quiz
1 / 3