What is the most efficient way of loading m boxes of soda into your fridge, each with n cans? The way I used to do it was open one box at a time and load the sodas in one by one. Then once I learned more about Big O and runtime complexity, I realized there is a more efficient way to load sodas into your fridge.


Time to learn how to load sodas efficiently

The naive approach

Take a look at this naive implementation of loading sodas into your fridge:

  • For each soda box:
    1. Open the box
    2. For each soda:
      • Load the soda into the fridge

That means for m soda boxes and n cans, it would take O(m*n) time to load the sodas into the fridge.

The more efficient approach

What if instead, you were able to load all the sodas in one step, regardless of how many sodas were in the box? You can load all the sodas in at once by:

  • For each soda box:
    1. Open one side of the box
    2. Place the box in the fridge
    3. Open the other side of the box
    4. Hold the cans in place with one hand
    5. Slide the cardboard out with the other

Comparing the runtimes

I want to say we turned an O(m*n) algorithm into an O(m) algorithm. Technically, it was O(m) the whole time, since n was almost never bigger than 12 or so. And since n was a constant, the whole algorithm was always O(m). Still, it practically feels like loading sodas in one at a time is a linear operation, while loading sodas in by pulling the cardboard feels like a constant time operation. If you assume that, then we did turn an O(m*n) soda loading operation into an O(m) operation. And then later you can enjoy a nice cold can of soda with the extra time you bought.