Question

Suppose you are given a stack of n pancakes of different sizes. You want to sort the pancakes so that smaller pancakes are on top of larger pancakes. The only operation you can perform is a flip—insert a spatula under the top k pancakes, for some integer k between 1 and n, and flip them all over. Describe an algorithm to sort an arbitrary stack of n pancakes using O(n) flips. [Hint: This problem sounds a bit like the "Tower of Hanoi" probem that you may have encountered in other classes. But don’t be fooled! The solution looks very different.]

Answer 1

We will use the following approach to solve the problem:

Step-by-step explanation:

1. We will identify the largest pancake in the given stack of pancakes, then insert the spatula below that pancake and flip the entire stack consisting of that largest identified pancake and all other pancakes on the top of it. Now the largest pancake will be on the top of the stack. Now insert the spatula at the bottom of stack and flip. In this way the largest pancake will become the bottommost pancake.

Now identify the next second largest pancake and repeat above process, keep on relating that until all are sorted.

This requires almost 2n-3 flips in worst case. ( For n pancakes). So the time complexity is O(n)

2n because one flip is required to bring pancake at top, then in 2nd flip it goes to bottom.

-3 because, the stack becomes sorted once the 2nd last pancake comes to the top. So next three steps are never required.

B) we want to find stack of n pancakes, that take omega (n) steps.

For that to happen, in worst case ( 2n-3 )>= cn , taking c=1

2n-3 >= n , => n >=3

So for n greater than or equal to 3 the condition holds.