Hacker News new | past | comments | ask | show | jobs | submit | duncanwest's comments login

You say it will take on average n! attempts to find a sorted list randomly. This is false. It will take on average n!/2 attempts.


O(n!/2) == O(n!), the whole paragraph is obviously referring to big o notation.

edit:( I have edited the post to respond to your comment, trying to clarify what OP meant; I in no way tried to make your comment "look silly" )


Yes, but that's not what he says. He says "The loop will repeat on average n! times". That's not true. He's not referring to O notation there, he brings that in later. Here he's talking about the imperative number of times a loop will run on average.

Edit: you've edited your paragraph to make my reply look silly. The whole paragraph is not in O notation. In fact - the exact opposite. In the last sentence of that paragraph he shows what the expression with constant factors looks like before converting it into O notation, and it's wrong! "The product (n-1)n! is O(n × n!)." Bzzzzzzt! Wrong! He should say "The product (n-1)(n!/2) is O(n × n!)."


True, but that's still O(n!), so the overall complexity doesn't change.


The mean would certainly be n! (note that it is possible, and even likely, that you may create the same sorting multiple times by random chance).

The median, which I don't think you're referring to, is something else (I imagine it would be substantially less than the mean).

(See http://en.wikipedia.org/wiki/Geometric_distribution)


Why be cruel to designers with your silly joke?


Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: