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!