Find the Big-O notation explained for not-so-technical people from Codility’s very own Head of Engineering, Marcin Kubica, Ph.D.
Setting the scene
Painting a pyramid
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.