Algorithms to Live By: The Computer Science of Human Decisions

by Brian Christian

So in the worst case, where the shelf is perfectly backward, at least one book will need to be moved n positions. Thus a maximum of n passes through n books, which gives us O(n2) in the worst case.*