A note on the complexity of a partition algorithm (Q788493)

In this paper we present the results of the theoretical analysis of a simplified version of the partition procedure PARTS described by \textit{E. Horowitz} and \textit{S. Sahni} [J. Assoc. Comput. Mach. 21, 277-292 (1974; Zbl 0329.90046)]. Its worst-case behavior is shown to be strictly exponential. On the other hand, for \(x_ 1,...,x_ n\) chosen at random in an initial segment of positive integers, we show that, with a probability close to 1, the computation time of PARTS grows as ex\(p\{\) \(c\sqrt{n}\}\).