Don, you missed my comment saying you could bound the randomized algorithm in the same way to n/4+1 by keeping track of where you pick and if you find n/4+1 0s in one half you conclude it is in the other half.
I wouldn’t say that a randomized algorithm is better per se, just more generally useful than the a particular deterministic one. You don’t have to worry about the types of inputs given to it.
This case matters because I am a software creator and I want to reuse my software components. In most cases I don’t care about performance of every little sub component too much. Sure it is not “optimal”, but me spending time on optimizing a process that only happens once is not worth it in the real world!
Obsessing about optimization is not always the way to win.
Don, you missed my comment saying you could bound the randomized algorithm in the same way to n/4+1 by keeping track of where you pick and if you find n/4+1 0s in one half you conclude it is in the other half.
I wouldn’t say that a randomized algorithm is better per se, just more generally useful than the a particular deterministic one. You don’t have to worry about the types of inputs given to it.
This case matters because I am a software creator and I want to reuse my software components. In most cases I don’t care about performance of every little sub component too much. Sure it is not “optimal”, but me spending time on optimizing a process that only happens once is not worth it in the real world!
Obsessing about optimization is not always the way to win.