Comment Solution? (Score 3, Interesting) 260
Assume we are stacking pancakes with largest at the bottom.
- Find the largest unsorted pancake
- Flip that to the top
- Flip from the bottom-most unsorted pancake. (One additional pancake is now sorted)
- Repeat until sorted
To me, assuming that you consider "Find the largest unsorted pancake" to be O(N), the algorithm is O(N^2). Number of flips is 2N. Where's my turing award?
So I must be missing something... Is one not able to find the largest unsorted pancake easily? Perhaps you are only able to look at the size of the topmost pancake. The article was unclear.