The worst case is of course infinityOriginally posted by Salem
Yeah, actually it doesn't have an O value as such.
It is a probablility, that being 1 : N! of actually coming up with the right answer in any given trial.
The average time till success is N!.
Let NS be the time to success ( i.e., getting a sorted deck).It is easy to see that
P(NS=i)=(1-(1/N!))^(i-1) * (1/N!)
The expected value of NS is N!