Suppose that every atom in the known universe had a unique serial 
number. Suppose I picked a serial number at random, and then asked you 
to go find out where that particular atom is. (Let us assume that there 
is no particular correspondence between serial numbers and position in 
space.)

Well your first problem is going to be that if I pick a random serial 
number, that atom is probably many billions of light years away from 
Earth, and so even if you knew where to go, you couldn't possibly go 
there. But suppose you somehow have access to an electronic database of 
all the atoms, their serial numbers, positions, and other interesting data.

(We casually ignore for the moment the minor detail that a database 
describing the known universe would obviously be very much larger than 
the actual universe itself, and hence could not possibly exist inside it...)

Given such a database, there are two ways you could try to find this atom.

One is to simply go through the database table, one row at a time. This 
is equivilent to examining every atom in the universe, one by one, until 
you find the one you want.

Assuming that you could somehow examine several million million million 
records per second (highly implausible), to find the atom you're looking 
for would take... several tens of billions of times the current age of 
the universe. As in, after all the energy in the universe had been spent 
and the entire cosmos had died an icy death of silent stillness at zero 
entropy, your hypothetical computer would still have not made 1% 
progress yet.

Just stop and think about that for a moment. There literally isn't 
enough time in the universe to perform this search. Woah.

(But hey, you're searching all the atoms in existence! It's hardly 
surprising...)

Alternatively, you could perform an index lookup. Assuming you have an 
index on the main table that consists of a tree with 10 entries in each 
node, you could find the atom in question after examining... 100 nodes. 
(If we assume the tree is well-balanced.) Even if we type in the index 
node requests by hand, it will take well less than 10 minutes to find 
out atom.

So, one way has O(n) complexity, and would take so long that there 
simply isn't enough time or energy in the universe to complete the 
computation. The other way is O(log n), and would take less than 10 
minutes even if done partially by hand.

Wow. Just... wow.

Post a reply to this message