There seems to be a lot of disagreement about lower bounds here. The best case lower bound is trivially 0 since you could start with a terminating permutation. The article is talking about a worst case lower bound, which is what one would use to assign the problem to a complexity class.
