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. Also, in his list, 23 precedes 19, so it’s not sorted. I’m not sure if that’s part of the joke.

  2. Not to mention that creating lunch out of nothing really is miraculous, and much more impressive than sorting numbers, so I’m not sure why that frustrates Him.

  3. I’m not sure I understand the first miracle. If someone gave me a list of numbers and told me to sort them, I could. And I could do in in linear time because that’s the only kind of time that I exist in. Am I…Jesus?

  4. Dysfunctional: “linear time” has a specific meaning in maths (specifically, in computer science). SMBC is very specifically targeted at nerds. (Wienersmith routinely addresses his readers as “Hey, nerds!”)

  5. So linear time as opposed to exponential time I’m assuming; the problem is that the given set is random, so it’s not impossible to solve a given set in linear time, it’s just you can’t on average solve a problem in linear time. So he got lucky and solved a set that was already in order, or close to it. Linear time is a subset of exponential time when the exponent is 1.

  6. larK there are other orders of time-complexity commonly arising in this sort of problem, between linear and exponential. For example, quadratic. Also common (and comes up for sorting!) is n log n, which would be between linear and quadratic.

  7. Carl: “If something has been proven impossible by math, doing it violates logic. Math is logic.”

    But my point is that it’s not really proven impossible by math. It’s only impossible given certain assumptions – e.g. that you don’t know the distribution of numbers in advance, that you sort by doing comparisons of single numbers, that you can only do one comparison at a time, etc. . . If a powerful being had a black box that sorted in O(n), I would assume that they had a way of bypassing those assumptions, not that they were violating math/logic.

    Lark, related to your point, what does it even mean to say that you sorted a single list in linear time? The difference between O(n) and O(n^2) (for example), is how the time grows with n. You can’t observe the function with a single sample. e.g. if I take 7 minutes to sort a list of 500 integers, how can you say anything about the time complexity?

  8. Winter — thanks for jumping in and clarifying some matters. Also for putting the “on the order of” back in, which is the way this kind of complexity is always studied.

    But I would add (probably in agreement with you, but it’s not obvious) that “divine insight” or “magical solving power” or … ahem … “quamtum computing” … are not outside the are of theory. These are pretty much what is meant by “nondeterministic algorithm”. But the solution still needs to be checked / verified / transmitted and authenticated / and a time complexity can be given for that too, separate from the solving complexity. If the checking can be done in polynomial time, we have a “nondeterministic polynomial-time algorithm”; and the set of all such problems (sets) is the “Nondeterministic Polynomial” or NP set.

    As mentioned in the famous unproven conjecture P = NP (where P is the set of all problems with Polynomial time deterministic solution algorithms).

    larK — As Winter pointed out, the complexity is not calculated by best case, or average, but in a way by worst case.

    I should distinguish by mentioning whose complexity we are talking about. The comic and this discussion have been mostly about the complexity of some particular algorithm for a problem. And that is indeed measured by the performance on the worst case. So typically a proof (or exercise answer) will begin by saying “Feed the algorithm an input of natural numbers in reverse sorted order” and then prove that the algorithm in question is pretty bad and will need O(n^2) steps.

    But we can also ask about the complexity of a problem, and then in a sense we are going for a best case measure — the complexity of the best algorithm for this problem. (This might be “best known so far” or “provably best”.) So a sorting algorithm based on comparisons must use time at least O(n lg n).

    (Of course, you can be interested in defining and calculating/proving an average performance of an algorithm over a distribution of inputs. But this is not generally what one means by the complexity of an algorithm or a problem.)

    BTW – Linear time is a subset of exponential time when the exponent is 1. Sounds like possibly mixed up about exponential. Exponential is not O(n^const) where indeed when the constant is 1 you have linear. Rather, exponential is in general O(e^n) where our variable is in the exponent. Or often O(2^n) in computing, since things like length of input are measured in binary. The lg above, by the same token, was not a typo but a notation convention for log base 2.

  9. When I was in grad school in Computer Science, computational complexity was new and hot, and we computed the complexity of everything, including making a sandwich. Complexity is in the number of operations, not time per se, and has been mentioned is worst case. So parallelizing the problem doesn’t affect the complexity, though it might reduce the time.
    I just did an article analyzing the computational complexity of doing jigsaw puzzles (n**2) so I still have the bug.

  10. Thanks, Scott.
    Complexity is in the number of operations, not time per se,
    Yes, of course, but it is not uncommon to say “time” meaning number of operations. There are also people who will say “space” for memory requirements!

  11. Mitch — what I am getting at (and I think WW is too), is that the way the problem is presented in the cartoon, while alluding to all the computational complexity that you are talking about, is actually not presenting any of that; it is simply presenting one instance and claiming that because he was able to sort this particular list, it disproves all the complexity theory you are citing. But one solution does not prove (or in this case even disprove) the general case. No need to delve deeply into complexity theory, it’s a red herring.

  12. larK, I happily can agree entirely — with what you say this time. But previously it seemed you would countenance that he would have demonstrated something important had he sorted one average input in linear time. That ought to still be tossed out on the basis you give now, that a single instance doesn’t do anything for the general case. So I am misconstruing your remark about average, and am glad to have that corrected!

    (Tangentially,) We are all bypassing a possible shorthand or shortcut in his exposition. Perhaps the claim is really that he has an algorithm which can always, even in the worst case inputs sort any list into numerical order. And he illustrates his claim by performing that job — even over and over if asked. Of course, that is not a proof, even yet. But it ought to set the mathematicians and theoreticians to worrying!

  13. Mitch says: ” We are all bypassing a possible shorthand or shortcut in his exposition. Perhaps the claim is really that he has an algorithm which can always, even in the worst case inputs sort any list into numerical order. And he illustrates his claim by performing that job — even over and over if asked. ”

    1- I think you left out saying “in linear time”.
    2 – Even this much does not yet overthrow the math of algorithmic complexity. That applies to deterministic algorithms, as I think one of you debaters brought up earlier. So he would have to be asserting that he secretly has a deterministic linear-time sorting algorithm . And one good response would be, Then trot it out please.
    Or else he has a non-deterministic algorithm. That’s fine with the math, which only says anything about deterministic algorithms.

  14. Mitch — I confess totally to hand-waving in my earlier response; I guess I shouldn’t have tried to couch it in terms of math. I was merely trying to say that what we are dealing with in the cartoon is one single instance, and that doesn’t prove anything. I was trying to do something analogous to plugging in zero to a big hairy equation — it makes it easy to solve, but it doesn’t prove anything — one specific instance being easy doesn’t mean the general case is.

    And yes, I read the cartoon as him touting this one specific case: I was given this large randomized set of numbers, and I put them in order — so there! He does not seem to me to be saying I can solve this type of problem generally, he’s saying I solved it once, for this specific set. Whoopee — maybe by chance they were already order, or nearly so.

  15. Danny – thanks, I did leave out “linear time” in one of those statements. And I agree that in my (Tangentially,) even a reliable repeat performance, though impressive, though astonishing from a math perspective would not undermine the math the way a proof (or open demo of an algorithm) would. And yes, there would still be an out, in us saying “Oh, the math does not apply for nondeterministic algorithms”.

    larK – also thanks for clarifying, and I still agree that a single demo would not mean anything definitive. While we agree that the cartoon indeed shows him sorting a single instance, as my (Tangentially,) tried to raise, it could be re-imagined to show a series of trials and an assertion that he could always do it that way.

    Winter – When you say an algorithm that, on average, could sort in O(n) that seems to be talking about a series of trials, over which an average is taken of the performances. Well sure it would be impressive! Everybody would be scratching their heads, or demanding he say what the algorithm is (if deterministic, that is, plus the other conditions you mentioned earlier, such as comparison-based).
    That’s slightly different from a single trial, on “an average input” (if that can be given operational sense). That’s what I thought we were dealing with earlier, though when I look back at larK’s first formulation he says ” you can’t on average solve a problem in linear time” and that could well mean multiple trials. But if a single trial, once again, impressive yeah, but the first thing to say is “Okay, do it again please”.

    An algorithm:

    solution-array = make-array(length(input-list))
    While length(input-list) > 0
        i = pop(input-list) // which decrements length(input-list)
        index = ConsultOracle(i)
        solution-array[index] = i
    result = solution-array

    Easy to see this runs in O(length(input-list)) — though we should have said something about the size of the allowed entries.
    Harder to see that the result is correct, which we also kind of want 🙂 . But that depends on ConsultOracle. Which may be, say, unit cost, if we are indeed plugged into the supernatural.

  16. Okay, here is my refinement on your algorithm:


    solution-array = make-empty-ra-array(length(input-list))
    working-list = copy(input-list)

    While length(working-list) > 0
        i = pop(working-list) // which decrements length(working-list)
        index = ConsultOracle(i,input-list) // original input-list is an argument to oracle
        solution-array[index] = i

    result = solution-array

  17. “Isn’t “leftovers” a way of creating lunch out of non-lunch?”

    Well, in that case, creating any meal is a miracle. Food is not a meal until it is prepared and that prepared food is given a name (usually related to when it is to be consumed). The steaks in my fridge are not “dinner” until I transform them but cooked them to eat as the evening meal. So all cooks are divine. Which I will agree with.

  18. Mitch: Yep, I meant an average over trials. I thought you were complaining that order of operations should never be defined as an average over inputs, but only as worst case over inputs. So I think we’re pretty much all on the same page, and just misunderstood each others comments.

    I’m actually not quite sure what it would mean to have a single trial on an “average input.”

  19. Sorting in linear time is easy. Just do the following:
    Get a box of spaghetti. Go through your list of numbers. For each number, take one strand of spaghetti and cut it to a length proportional to the number.
    Then gather up all the strands into a single cylinder and hold them in your fist so that they are all upright with one end resting on the table.
    Then repeat the following:
    take out the longest strand and put it in the output tray to the right of any other strands in the output tray
    until all the strands are in the output tray.

  20. As for the joke proper: Read once that Will Rogers, when better known as a “Ropin’ Fool” rather than a humorist, would lasso all four legs of a running horse. He’d top it by lassoing just two legs — a tougher trick. But non-cowboy audiences figured that two legs was easier than four, so Rogers often reversed the order and made four legs the topper.

    Here tis: https://www.youtube.com/watch?v=1pmGcmgvwqY

  21. MiB’s spaghetti-fist method is reniniscent of classic illustrations of what an ANALOG computer is/does.
    At one time the concept was a commonplace contrast pair with DIGITAL computing.

  22. While I’m impressed with how many people here are computer scientists, I think you guys kinda left the laymen behind without explaining.

    In that murky place where the border between mathematics and computing is fuzzy, we have the field of computational algorithms — an algorithm being a series of steps taken to solve a problem. One of the hardest basic operations is sorting a list of arbitrary length and randomness.

    The most elementary way to sort such a list algorithmically is to go through the entire list and compare pairs of numbers, swapping them if they’re out of order. This is called “bubble sort”.

    The problem is one pass through the list isn’t enough — not even close. After one pass, the only number you know is in the right spot is the last one. Then you need to go through almost the entire list again. And again. And again. And again. It turns out you need to go through the list the same number of times (essentially) as the number of items in the list.

    So if you have a list of 100 numbers, you need to compare/swap 99 pairs (round that off to 100), and you need to go through the list 99 times (round that off to 100 too). That’s on the order of 10,000 comparisons/swaps. 10,000 can be done real quick by modern computers, of course, but that’s not the point. Since the number of comparisons goes up with the square of the number of items in the list, it means that really long lists start to take way too much time.

    We notate that by saying the complexity is on the Order of the square of the Number of items — O(n^2).

    O(n) would be the Platonic ideal complexity — just one pass through the list and everything is sorted. If you can figure out how to do that, you’ll be famous forever. Or God.

    Between O(n) (impossible ideal) and O(n^2) (worst non-contrived case) there is a whole lot of wiggle room, room that makes a big difference when you have big numbers. And coming up with new sorting algorithms is a major task in computer science — as is determining their complexities.

  23. Still thinking about this one… note that Jesus says that he has sorted “THIS” list in linear time. He didn’t say that he came up with an algorithm that sorted AN ARBITRARY list in linear time.

    He may have just come up with an algorithm that says “take the eighteenth term and put it first, then the seventh and put it second, and the nine-third and put it third…” and the algorithm just HAPPENS to put THAT SPECIFIC random list in linear time.

    That’s not particularly miraculous. You could give me a randomly-sorted list of 100 terms, and I could write that linear-time algorithm. I would have to first sort the list myself, in something closer to n^2 time to figure out where each term was supposed to go, but after I did that and knew where everything was supposed to go, I could do that.

    So, yeah… it’s NOT that miraculous, is it? If he’s said that he’d created an algorithm to sort an arbitrary list in worst-case linear time, then THAT would be more impressive than tuna sandwiches for everybody.

  24. I’ve always thought the real miracle of The Loaves and Fishes was that Jesus apparently didn’t get any complaints from the crowd on the order of “I hate seafood, could I just have a cheese sandwich instead?” or “Is that white bread? I only eat whole wheat, and non-GMO of course” and so on and on.

  25. So Mitch, what ianosmond just said is what I was trying to say; clearly I shouldn’t have tried to be clever, it just blew up in my face.

    Honestly, I think this cartoon is a case of the author over-reaching and throwing something in he doesn’t quite understand, and hoping he can fool the readers into thinking he knows more than he does.

    I’m reminded of even the great Douglas Adams over-reaching himself, at one point, to show off how smart Marvin is, and how nobody appreciates him, he had Marvin mumbling about how he had found an answer to the square-root of minus 1, how it was supposed to be impossible, and about how he had found the answer. Well, yeah, it’s called i, and it’s not unknown, and it’s not so much an answer as Adams was positing it (a (real) number that somehow miraculously squares to -1 (42, maybe?)) — it is a simple placeholder for a whole new aspect of mathematics, calling it i is as good as anything, and me telling you the square root of -1 is i really doesn’t tell you anything. But once you start doing math with i, suddenly whole new worlds open up. I hope that Adams eventually learned about the wonders of complex numbers; the joke, as it was, fell about as flat as when people would ask my math major friend to do big arithmetic problems.

  26. ianosmond/larK: But even allowing the cheat of a custom-built algorithm, in what sense can a single run of an algorithm on a single set of data be said to run in linear time? In what sense could it even fool someone into thinking it was a linear time algorithm? “Linear time” is a statement about how it scales with n. You can’t observe how something scales with n for a single value of n.

    e.g. if your (or Jesus’ [1]) algorithm sorts a list of 100 terms with 500 operations, I don’t see how you (or Jesus) can claim that’s done in “linear time.” Those specific results are consistent with 5n, 2.5log_10(n)n, and 0.05(n^2). You could fool someone into thinking it was particularly fast, if it was a programming competition, and everyone else’s algorithm took over 600 operations. But you still wouldn’t have done anything to fool them into thinking it was linear time.

    [1] It’s always fun to have the rare excuse to form a posessive without the work of an extra ‘s’ at the end!

  27. larK: “…the joke, as it was, fell about as flat as when people would ask my math major friend to do big arithmetic problems.”

    When I was an undergraduate, the convention when people went out to eat was that the youngest non-math-major had to figure out the bill. The “youngest” condition was the standard “give annoying tasks to those with less seniority” condition seen around the world. The “non-math-major” condition was added on the grounds that math majors particularly hated, or were bad at, anything that involved actual concrete numbers.

  28. [1] It’s always fun to have the rare excuse to form a posessive (sic) without the work of an extra ‘s’ at the end!

    That’s not universally accepted. Many, and I include myself, only think it’s proper to drop the second ‘s’ when the word is a plural. Not that there’s any kind of authority, so you do as you think correct.

  29. Sure, but it’s generally accepted that there are a number of authorities that make an exception to that rule for Jesus. So you have something to point to if your teacher puts red mark next to the “Jesus'”

    Similarly to the serial comma, YMMV, depending on the authority consulted.

  30. When I was “writing tutor” (not fully a TA!) for the “Philosophical Perspectives in the Humanities” core course, I had to face this issue with our students over Socrates . After trying to dodge with the suggestion of saying the views held by Socrates or the argument advanced by Socrates I capitulated into their use of a possessive, and accepted that this name (and some other classical names, with certain phonological patterns) were also exceptions to the add-S pattern and could follow the model of Jesus.

  31. Re waltmorris’ comment about a comma after the first 2, enlarging the image reveals a faint comma.

  32. Okay, I was a programmer for a quarter of a century, and although I understand the basic math involved in calculating the costs of the various sorts, I never had to write a sort for work, we had external routines for that (this is old timey COBOL and such, languages didn’t have sort functions built in.) But it seems to me, if Jesus is God, and God Is omniscient, then he would know the correct placement of each number in the list and could very easily sort the list in one pass. Is that not linear? In a very simplified example, you have a list of unique numbers 1 through 100. Read the first number n and store it in an array (scalar, whatever) index n. Continue through the list. You now have an array of numbers in ascending order. Yeah, it only works because you already know that’s where the number(s) will end up, but that’s the whole point of being omniscient.

  33. Guero, in light of this comment, may I point you back to one I posted yesterday, with a routine in “code print” and a nonspecific algorithmic language?


    solution-array = make-array(length(input-list))
    While length(input-list) > 0
        i = pop(input-list) // which decrements length(input-list)
        index = ConsultOracle(i)
        solution-array[index] = i
    result = solution-array

    (See also a followup post by Danny Boy that he called an improvement – it does tidy up some things.) Is this not what you are describing?

    OTOH, in doing it this way, we are not taking into account Winter Wallaby’s comment this morning that a single run cannot properly be called linear. That term, recall, means that a graph of a function is a straight line — and we have just one point to graph, not a function (steps required against length of input). That’s why we need to generously interpret the cartoon as leaving out him saying this is a demo and he can repeat it at will on new inputs.

  34. Well, in my defense, I typically zone out when reading algorithms. I got a chuckle with the ConsultOracle() function, but my mind went to the old cartoon with the two scientists in front of a blackboard filled with equations, and one scientist is pointing to a blank spot on the board saying, “and then a miracle happens here.” Which, in fact, brings us full circle to the cartoon.

  35. Guero, I remember that cartoon as well! (I hope one of our archival-inclined participants may dig it up and post it!) That is indeed the idea behind the consultOracle() function.

    Of course, putting a call to an oracle in your algorithm is not an original idea with me. It’s something that gets studied in mathematical computer science (complexity etc) along with the other ideas we have been brushing up against. It is not exactly the same as “nondeterministic turing machine” classifications. Because, unlike the way I was using it here, the oracles are not used for “the whole thing” of a task being studied, but just “a known hard part”. For instance, telling you (in small constant time) whether an input number is prime. There is still something complicated you may be doing with that answer, or with that number in different ways depending on the oracle answer.

  36. I follow the Strunk and White rule that “Biblical and Classical names that end in s just get the apostrophe” because I love how stupid and arbitrary it is. I love that, if I’m talking about the stuff in the parable, it’s “Jesus’ fish”, but if the first baseman for the Miami Marlins goes fishing, it’s “Jesus’s fish”. Or “Moses’ law” for the guy in the Bible, but “Moses’s rebound skills” for Moses Malone. And that you can start fighting about the exact year you switch over. It’s so silly. I am absolutely keeping such a ridiculous rule.

Add a Comment

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

WordPress.com Logo

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

Twitter picture

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

Facebook photo

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

Connecting to %s