4 ms·
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.
by duncanwest 13y ago
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.
- deletes 13y agoO(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" )
- duncanwest 13y agoYes, 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!)."
- aquamongoose 13y agoTrue, but that's still O(n!), so the overall complexity doesn't change.
- thetwiceler 13y agoThe 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 http://en.wikipedia.org/wiki/Geometric_distribution)