Deus in Machina?

I was struck by the similarity of these two recent essays:

• The God Login

  we need to understand the code that's out there, grok why it tends to be fast or slow due to the tradeoffs chosen, and choose the correct algorithms for what we're doing. That's essential.

  And one of the coolest things Mr. Pausch ever taught me was to ask this question:

  What's the God algorithm for this?

  Well, when sorting a list, obviously God wouldn't bother with a stupid Bubble Sort or Quick Sort or Shell Sort like us mere mortals, God would just immediately place the items in the correct order. Bam. One step. The ultimate lower bound on computation, O(1). Not just fixed time, either, but literally one instantaneous step, because you're freakin' God.

• Erdős’s Book and the Asymptotic Religion

  as even Barack Obama knows, if you implement Quick-Sort, with its running time of {O(n\log n)}, it would run faster than the {O(n^2)}-time algorithm Bubble-Sort.

  ...

  So why do we care about getting asymptotically good algorithms? Every TCS graduate student should be able to recite the “party line” answer that it has happened again and again that once a problem has been shown to be in polynomial time, people managed to come up with algorithms with small exponents (e.g. quadratic) and reasonable leading constants. There is certainly some truth to that (see for example the case of the Ellipsoid and Interior Point algorithms for linear programming) but is there an underlying reason for this pattern, or is it simply a collection of historical accidents?

  Paul Erdős envisioned that “God” holds a book with the most elegant proof for every mathematical theorem. In a famous quote he said that “you don’t have to believe in God, but you have to believe in the Book”. Similarly, one can envision a book with the “best” (most efficient, elegant, “right”) algorithms for every computational problem.

Did Erdos get the notion from Pausch? Or (more likely) did Pausch get it from Erdos? Or did they both get it from someone else, long ago?

They aren't really the same idea, anyway: Barak is talking about how, abstractly, you can simply assume that there exists a "best" algorithm, even if you don't know what it is, while Atwood is talking about how, abstractly, you can simply assume that there exists an omnipotence that isn't bound by any physical realities and use that to define a perfection that your algorithm can strive toward.

Similar ideas, but certainly different.

Regardless, they're both fun essays, and both do a good job of describing the value of arguing from the asymptotic ideal.