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?
The 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).
I 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.
