**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 …**

## Setting the scene

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 ladder **and** an extension pole.

I soon realized that painting 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 notation of time needed to paint either the attic or the pyramid.

## Painting a pyramid

The pyramid’s base is a square with sides *N* meters 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 notation of the cost.

The surface to be painted is clearly *O*(*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’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.

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 in 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 …

*This blog originally appeared on Cubical Thoughts.*