PancakeComputer Science Level 3
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
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.
Let the number of flips you need to perform be \(n\). What is the complexity of this algorithm?