fubarobfusco comments on Decision Theories: A Semi-Formal Analysis, Part I - Less Wrong

21 Post author: orthonormal 24 March 2012 04:01PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (90)

You are viewing a single comment's thread. Show more comments above.

Comment author: fubarobfusco 27 March 2012 11:52:15PM -1 points [-]

If you're given the algorithm to begin with, this doesn't seem like a big issue. But if I give you some code, which is an implementation of bubble sort but not labeled as such, then proving it takes quadratic time is more involved, and may (will?) require running the code. Right?

I'd say it's easier to prove that a naïve bubble sort runs in quadratic time, than it is to prove that when it terminates, the list is actually sorted. It's obvious by inspection that it contains a nested loop over the same data structure.