A magician approaches you and asks, “Excuse me, have you ever played 20 questions? As a magician, I have spent my life counting every atom in the universe and I now know how many there are. As a secret between just us, there are one hundred quinvigintillion atoms in our universe. Please pick a number between 0 and the number of all the atoms in the universe. If you give me 20 minutes of your time, I promise I will be able to guess your number. The only rule is that - similar to 20 questions - I can ask you simple yes or no questions until we arrive at an answer.”
At most, how many questions would the magician ask? This is an example of binary search cosmological scale.
In between my light laments over the hollowing out of any type of soul or perspective on engineering culture in the software industry (I’m looking at you endless middle and senior tech interviews that require rote manual regurgitation of algorithms even in the age of AI code assistance), I love thinking about the boundary conditions of time and spatial complexity. For myself, this helps me visualize the concept and have have more texture as to its deeper essence. The YouTube channel 3Brown1Blue does an amazing job of this for fostering an intuition for the geometric interpretation of math.
Recently, I’ve been thinking a lot about logarithmic functions and what the power of O(log n) truly looks like. I know the function is a powerful transformation from an exponential space to a linear space, but what does that look like in practice in the most extreme scenarios?
Enter the Binary Tree of the Universe (pending trademark). If we were to take every atom in the universe and put it into a binary tree for conducting binary search, how many steps would the search process take?
[Already familiar with Binary Trees? Skip this paragraph] For those unfamiliar with binary trees, they are a data structure that enables fast searching through a dataset by asking yes or no questions about that data that divide the possible results in half at each step. For example, if the magician had chosen an arbitrary number between 1 and 100, and we needed to guess it in as few attempts as possible, a poor question to ask would be whether the number was 50. A better question would be whether the number is greater than 50! If the answer is no, we can then assume the answer must be between 1 and 50. We can repeat this process by asking if the number is greater than 25, and so on and so forth until we locate our secret number. The Korean Bottle Cap Game (병뚜껑 게임), an excellent drinking game that uses the secret number in soju bottle caps, is an example of this phenomenon! While the objective is not to get the number, a clever competitor will use the reduction of the search space to quickly trap other competitors with binary search. We can formalize this in an easy-to-access data format that makes conducting these yes / no questions blazing fast, which is the binary tree.
Our current estimates for the number of atoms in the observable universe is 10^80 according to a current radius of ~46 billion light-years.
Converting this to a power of two:
log₂(10) ≈ 3.322
2^(80 × 3.322) ≈ 2^265.76 ≈ 2^266
Neat! So we have 2^266 atoms in our observable universe. 266 is conveniently close to 256, giving us a little bit of a memory cue for remembering how many atoms are in the universe for powers of 2.
According to what we can currently see, the universe is flat. There is no evidence that it does not continue on either infinitely or for such a gargantuan distance we cannot detect the curvature of the observable universe.
For the sake of this thought exercise, let’s assume it is indeed finite and we are a bubble in a greater hyperspace that is orders of magnitude larger than we can observe. We’ll also assume that each observable universe bubble is akin to a solar system with a star. If there were an observable universe for every star we can see within our own observable universe, how many atoms would we have?
~10^24 stars (1 septillion, significantly less than googol)
Powers of 2: ~2^80
2^266 * 2^80 = 2^346
So we have 2^346 atoms if every star in the observable universe represented another observable universe!
This is an astoundingly large figure - roughly ~10^4 larger than a googol. And yet, if we have built our binary search data structure using a perfectly balanced tree, it would only take us 346 steps to find our atom.
That is nothing.
If we optimized for disk reads, a la a modern database, and used a B-tree with a wider fanout and shallower depth, the total steps would be even less! To put that into perspective, the most famous staircase in the world, the Spanish Steps of Rome, has 135 steps.
In order to traverse our Binary Tree of the Universe to any atom in the observable universe, we would only need to ascend and descend the stairs in order to reach our atom. In the case of our every-star-is-an-observable-universe universe, we only need to climb back up the stairs once. And not even all the way.
That’s pretty cool. But can we go even more extreme while remaining finite? What if we had a universe-of-universes where every atom represents an observable universe, how many steps would it take to reach our atom?
2^532 = 2^266 * 2^266
It would take only 532 steps, or two up-and-downs of the Spanish Steps! Let’s compile this all into a handy reference table:
| Scenario | Powers of 2 | Powers of 10 | Binary Search Steps | Spanish Steps Equivalent |
|---|---|---|---|---|
| Stars in observable universe | 2^80 | ~10^24 | 80 | Climb 60% of the way up |
| Atoms in observable universe | 2^266 | ~10^80 | 266 | Up and down (2 sets of stairs) |
| Universe per star | 2^346 | ~10^104 | 346 | Up, down, up again 76 steps (2.5 sets) |
| Universe per atom | 2^532 | ~10^160 | 532 | Up and down twice (4 sets of stairs) |
Even our most extreme scenario requires fewer steps to search than it takes to walk up and down a set of stairs four times, albeit they are quite famous so you may need to dodge a person or three.
This engenders the question of what practical difference exists between O(n log n) and O(n) for any fathomable application in our observable universe. We readily remove constants when setting our complexity bounds, and yet max(log n) ~= 266 for anything within the observable universe! Could we thus think of O(n log n) as effectively O(266 n) for any application within the observable universe? There are many scenarios where a constant c may very well be larger than log n! Let alone observable-universe-max(log n).
Our runtime cost for our Binary Tree of the Universe comes in the construction and modification of the tree, but who's to say the universe didn't pre-index itself during inflation, assigning each atom a unique id as it popped into existence?
Archimedes said, “Give me a lever long enough and a place to stand, and I will move the world.” Let’s stand on the shoulders of giants and extend the quote:
“Give me a lever long enough and a place to stand,
And I will move the world.
Give me a logarithmic function,
And I will put the world in the palm of your hand!”
This exercise has convinced me that the Computer Scientists that argue O(n) and O(n log n) are equivalent are onto something. The universe and logarithmic functions may be teaching us some practical lessons.
First, when and how we construct our tree is the hard part - something obvious to anyone who has had to index a sufficiently large database. Two, if the performance difference between O(n) and O(n log n) actually matters, constants are just as consequential. And three, everyone is just two flights of stairs from everything else in the universe.
--------
Part 2 of this series: Earth-scale log n vs Cosmological log n.