in reply to RE (tilly) 3: Fisher-Yates Shuffle
in thread Fisher-Yates Shuffle

So what you are saying (roughly) is that the branch takes O(n) time (it's tested n times) to save you O(log n) work on a task which would otherwise be O(n)?

With branch: O(n) - O(log n), still O(n)

No branch: O(n) - O(n) + O(log n), still O(n).

In the long run, branch or no branch, the time is still dominated by n calls to the random function.

Replies are listed 'Best First'.
RE (tilly) 5 (the point): Fisher-Yates Shuffle
by tilly (Archbishop) on Aug 30, 2000 at 14:48 UTC
    I was actually analyzing the win/loss of the branch.

    For large arrays, the overall running time is going to be O(n). No question. But will trying to skip useless swaps overall speed you up or slow you down? Well on large arrays you speed up on log(n)+O(1) times, and slow down all of the other iterations, so it is a loss.

    But doesn't change the overall big-O of the algorithm, just the constant.

[reply]

In Section Meditations