4 ms·
I must be misunderstanding the problem. Why is the lower bound on the number of operations not 1, since you have a 1 in n chance of turning over the "1" card as
by tonygonz 16y ago
I must be misunderstanding the problem. Why is the lower bound on the number of operations not 1, since you have a 1 in n chance of turning over the "1" card as your first operation?
- seles 16y agoThe lower bound indeed is 1, however higher lower bounds can be found. Here lower bound means that there exist a permutation that will take this many operations. Their goal is to find what the maximum number of operations assuming worst permutation. This is accomplished when the lower bound equals the upper bound. Proving lower bounds is easy they just need to give an example. Proving upper bounds is hard, somehow they have a way besides running all possible cases. (The article doesn't explain how and I haven't delven deeper).
- Brashman 16y agoI believe it is a lower (and upper) bound on the worst-case. The case of "1" begin on top is a specific case, that is obviously not the worst possible.