[Lowerbounds, Upperbounds]

Algorithms are everywhere.

This is not a post to argue for or against the big-O notation. Instead I just want to share an observation using a toy example.

Consider a dictionary data structure that supports access in logarithmic time. Suppose we have two implementations A and B where A is two times faster than B. (To make it precise but toyish, imagine an access takes $\log n$ time and $2 \log n$ time respectively where $n$ is the number of elements.)

How would this factor of two become important?

Well, when there is a hard upperbound on the amount of time allowed in an access, then the maximum number of elements that can be stored in A is actually the square of that of B.

It’s squared, not just doubled.

Now here’s something to think about. You can have a digital photo album that can store a maximum of two thousand photos or another one with four million photos. They are equally responsive on your computer. Which one would you prefer as a customer?

(Or, perhaps we can wait 18 months and be happy with the former one? :P )