I used to live in an attic. After a few years, I decided to refresh the paint on the walls. The first challenge was to calculate how much paint I needed — a task more complicated than it sounds.
The attic was 4.5 meters high at the highest point, so it made doing precise measurements very tricky. Luckily, all of the surfaces of the roof were slanted at the same angle of about 45°, so I just needed enough paint to cover the floor surface multiplied by √2, plus the surface of the side walls.
Although I could've asked a professional painter for a quote, I decided to bite the bullet and do it myself. It can't be too difficult, right? I knew the surface to be painted and how much time it should take.
At first I could dip my paint roller directly in the bucket containing paint. Eventually I would need an extension pole, and then a ladder. And then a ladderandan extension pole.
I soon realized thatpainting the ceiling is not the most time-consuming part of the job — it was wetting the paint roller and not making a mess of the paint tray.
That's when I really started to think about it. What if the attic was much larger? How would the complexity of the problem change?
To exclude scaffolding from consideration, let’s simplify the problem and consider a pyramid that'll be painted from the outside. After all, the shape of this particular attic ceiling is equivalent to the outside of a pyramid. And instead of climbing a ladder inside the attic, we can climb the pyramid’s sides. But all of these differences don’t change the Big-O of time needed to paint either the attic or the pyramid.
Painting a pyramid
The pyramid's base is a square with sidesNmeters long and the sides are equilateral triangles. You can hire painters to carry the buckets with paint and use paint rollers.
Now estimate the cost of painting the pyramid’s sides. We don’t need exact numbers, just the Big-O of the cost.
The surface to be painted is clearlyO(N^2). But you should already know, it’s a trap …
In both cases it sounds like painting requires time proportional to the surface to be painted. But in the attic, I was significantly slowed down by having to climb up and down the ladder to refill the paint-tray. As the size of the surface area increases, transporting the paint becomes more challenging and the time needed is not proportional to the surface.
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'sO(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 isO(1). And how about climbing up and down the pyramid? It’s a different story. If the painted area is at heightH, climbing up and down takesO(H) time.
Now imagine the part of the pyramid that is beneath the painted area. Its volume is alsoO(H), which is proportional toH.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 takesO(N^3) time, while painting alone takes onlyO(N^2) time. For large pyramids, painters would spend more time going up and down the ladder than they would actually painting the surface.
Painting pyramids is rather an eccentric type of business, but this example shows a more general truth: most projects don’t scale linearly. That is, doing the same work that's 10x larger scale can cost you more than 10x.
Simply put: there are elements that are negligible in a small scale, that can become dominating in the large scale. But this is a topic for another story …