Lesson 1 of 4
DESERT ROUTE TEST
What happens when the array grows?
DIRECT ADDRESS JUMP
Go straight to the requested index
work required1 calculation
FULL SCAN
Check each box in the worst case
work required5 checks
O(1) stays flat: the input can grow, but the work does not.
O(n) grows with n: twice as many boxes can mean twice as much work.
O(1) is constant time. The algorithm performs a fixed amount of work even when n becomes enormous. Array indexing is a direct jump.
Your call · What happens to an O(1) lookup when n grows by 1,000 times?