AI Hints
Home›DSA in Python Tutorial›Big O in Code
DSA in Python · Lesson 7 of 132

O(1) and O(n)

Constant and linear.

⏱ 2 min read▶ Video at 6:51🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

O(1) and O(n)
From the video: O(1) and O(n)
  • 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.

constant.pypython
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")
Output
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.

linear.pypython
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")
Output
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)
Next up: O(n²): Nested Loops — when work multiplies