Chris is famous for baking perfectly round pancakes but they all come in different sizes. The customers usually don't care as long as its delicious, but today this one customer demands the pancakes comes in order, that is the smallest one being the top of the stack.

Chris is very annoyed but he will do it anyway. After baking a stack of pancakes, he will use a spatula to flip some top section of the pancake. For clarity, see the illustration below

sorting pancake with a spatula

sorting pancake with a spatula

Your task is to sort the pancakes. First, you keep track of 1 stack PANCAKE and 1 queue ORDERED. While PANCAKE is not empty, perform the following

  • Flip the biggest size to the top.

  • Remove the top of PANCAKE \(x\) away and push \(x\) to ORDERED.

  • Flip PANCAKE

Let the number of flips you need to perform be \(n\). What is the complexity of this algorithm?


Problem Loading...

Note Loading...

Set Loading...