> "Note that you shouldn't use the algorithm in practice"

You certainly can:

1. Run the randomized algorithm

2. If if the usual way takes too long (more than O(n) for whatever constant factor makes sense to you), just stop doing more work and switch to the deterministic algorithm

Now you get the best of both speeds, within a small constant factor (like 2).