Get started

You may recall that I recently shared a simplified explanation of what the Big-O notation is, and why it matters. Let me share another relevant story with you …

Imagine that a painter picks up a paint bucket and roller, climbs the pyramid, paints some of it, and returns to the base. How much paint can they carry? I don’t know exactly, but it’s O(1) — which is “some,” but a limited amount. How much surface can they paint at once? Again, I don’t know exactly how much, but it’s proportional to the amount of paint that is O(1). And how about climbing up and down the pyramid? It’s a different story. If the painted area is at height H, climbing up and down takes O(H) time.

Now imagine the part of the pyramid that is beneath the painted area. Its volume is also O(H), which is proportional to H. Since each part of the pyramid is beneath the top surface, the total time it takes the painters to climb up and down the pyramid is proportional to the pyramid’s volume.

In other words, climbing up and down the pyramid takes O(N^3) time, while painting alone takes only O(N^2) time. For large pyramids, painters would spend more time going up and down the ladder than they would actually painting the surface.

Marcin Kubica is currently Head of Engineering at Codility. He has a Ph.D. in Computer Science and has previously served as a Professor in Computer Science.

Connect on LinkedIn