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

I got this question in class test.

My question is based upon Pancake Sort topic in portion Sorting of Data Structures & Algorithms II

Answer 1

Correct answer is (c) 2n-3 flips

The best I can explain: 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.