The general approach outlined in this paper in its proof of the lower bound on the average number of I/Os needed to obtain a given permutation of some input in external memory is as follows. Note that $N$ is the number of items to be permuted and $t$ has no prior definition in the paper.


Why are they trying to find the value of $t$ for which the bound on the number of possible permutations generated after $t$ I/Os is only $\frac{N!}{2}$ instead of $N!$? I realize that $\frac{N!}{2}$ gives the number of orderings of $n$ elements, but just because you can obtain one permutation after $t$ I/Os does not necessarily mean that you can obtain its reverse permutation after $t$ I/Os.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.