Question

How many flips does the simplest of pancake sorting techniques require?
a) 3n−3 flips
b) 2n-4 flips
c) 2n-3 flips
d) 3n-2 flips

Answer 1

Answer: c
Explanation: The minimum number of flips required to sort any stack of n pancakes has been shown to lie between 1.087n and 1.636n. using average of that 1.36n and extracting that for values of n>1. We have 1.36, 2.72, 4.08 etc. This matches best with 2n-3 which is equal to 1, 3, 5, 7, 9, etc. An upper bound of 2n-3 comes by iteratively using the next largest element in its correct place using two flips.