O(1) and O(n)
Constant and linear.
Let's put Big O into practice, starting with the two most common shapes. Constant time, which is always fast. And linear time, which grows with the input.

- Two common shapes
- O(1): always fast
- O(n): grows with input
Constant time
Getting an item by its position in a list takes one step, however long the list is. So does looking up a key in a dictionary. Both are O of one. Run it. A list with ten million items is just as quick to index as a tiny one.
import timeit
small = list(range(10))
huge = list(range(10_000_000))
t1 = timeit.timeit(lambda: small[5], number=1_000_000)
t2 = timeit.timeit(lambda: huge[9_000_000], number=1_000_000)
print(f"tiny list: {t1:.3f} seconds")
print(f"huge list: {t2:.3f} seconds")tiny list: 0.018 seconds huge list: 0.018 seconds
Linear time
Searching a list for a value is different. Python has to check the items one by one. Double the list, and you double the work. That's O of N. Run it. The bigger list takes about ten times longer, because it's ten times bigger.
import timeit
a = list(range(100_000))
b = list(range(1_000_000))
t1 = timeit.timeit(lambda: -1 in a, number=100)
t2 = timeit.timeit(lambda: -1 in b, number=100)
print(f"100 thousand items: {t1:.3f} seconds")
print(f"1 million items: {t2:.3f} seconds")100 thousand items: 0.046 seconds 1 million items: 0.466 seconds
Summary
Indexing a list and looking up a dict key are O of one. Searching through a list is O of N. Next, what happens when loops go inside loops.
Key takeaways- list[i] is O(1)
- x in list is O(n)
- dict[key] is O(1)