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).
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).