by Winter Wallaby

Violates logic itself?

Does this really violate logic? And which miracle is really more impressive?

It doesn’t seem to me that sorting a list in linear time really violates logic itself. It seems plausible that a divine being might be able to do any number of things that would violate the conditions that prevent sorting in linear time. e.g. perform multiple operations or comparisons at once. Or omnisciently perceiving the distribution of the numbers and then using it to perform a bucket sort.

I’m not saying that sorting in linear time isn’t impressive. But the crowd does have a point here. Violating conservation of mass does seem more impressive.

UPDATE

For SMBC fans who think the bonus panel and hovertext are essential to the comic, here they are.

“All technical quibbles may be sent to my email, where they will be figuratively burned.”

52 Comments

  1. Mitch4/guero: If you’re going to allow that God knows all things (which is reasonable), why not also allow that he can move more than one element at a time?:

     func sortArray():
      determineSortedPositions()
      moveEverythingToCorrectPosition()

    It’s O(1)!

    Scott’s point that complexity is in the number of operations, so that parallelizing doesn’t affect the complexity is well taken, but there is some ambiguity in what consistutes an “operation.” If for a divine being, moving multiple elements at the same time is no more “work,” then all the movements done in unison should count as an “operation.”

    For example, Grover’s algorithm, on average, finds an element in an unsorted database of size N in O(sqrt(N)) operations. That’s clearly impossible classically, but it’s possible because Grover’s algorithm is a quantum algorithm, and so its operations can perform steps on every element of the database simultaneously.

Add a Comment

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.