Data Structures

Big O notation explained: O(1), O(n), O(n²), O(log n)

Big O notation explained: how O(1), O(n), O(n²) and O(log n) describe the way an algorithm's work grows with input size, with Python examples of each.

  • 7 min read
  • 5 questions
  • +35 XP
Transcript

Big O notation explained by cats. Kitty counts treats. One treat, easy. 10 treats, still fine. A million treats, forever. Big O notation shows how time grows with size. What is O to the one? Kitty wants a fish. She grabs the first fish from the bowl.

One step, always. Doesn't matter if there's one fish or 1,000 fish. Kitty only wants one fish. That's O to the one. And O to the N? Now, Kitty has 10 fish. One is bad. Kitty not sure which. Kitty smell each fish until it finds a bad fish.

That's O to the N. What about O to the N squared? Now, Kitty wants to check which treats smell best together. For each treat, she sniffs all the other treats. Five treats means 25 sniffs. 10 treats means 100 sniffs.

As the pile grows, the effort explodes. That's O to the N squared. And lastly, O log N? Kitty is tired of sniffing. Kitty hides in a giant pile of boxes. You need to find her. Instead of checking every box.

You cut the pile in half, Kitty not here. Cut it in half again and again. Cut in half again and again until Kitty is found. That's O log N. Big O isn't exactly speed. It describes how efficiently Kitty works.