Is the analysis of FrogSort in Saturday Morning Breakfast Cereal correct?

Question

In a recent Saturday Morning Breakfast Cereal comic, the author describes an algorithm called Frog Sort for sorting a list of natural numbers. The algorithm is described in the comic, but for simplicity I've reprinted it here:

1. For each of the natural numbers to be sorted, make a box with that many flies in it.
2. Put a frog in each box.
3. While not all frogs have jumped out of their boxes yet:
   1. Wait for a frog to jump out of its box.
   2. Write down the number of flies originally placed in the box.
4. The resulting sequence of numbers is the original list of numbers, but in sorted order.

This algorithm makes the assumption that all frogs eat flies at the same rate. As a result, the first frog to jump from its box will be the frog that had the fewest number of flies to each, the second frog the second-fewest number of flies to eat, etc.

In the middle of the comic, a teacher asks the students "What is maximum step number?," which I interpret to mean "what is the maximum number of steps required for this algorithm to terminate?;" that is, what is the runtime of the algorithm? The student then answers "log_frog(boxes)."

Is this an accurate analysis of the runtime of this algorithm? Or is the author wrong?

Answer 1

This runtime analysis is clearly wrong; we can get a trivial Ω runtime of max(n_elements, largest_element) (since we have make n_elements boxes, and then each box takes as long to empty as the size of its contents). A sorting algorithm that took less than n time would be... very surprising.

If you want to find more analysis on the internet somewhere, this algorithm is equivalent to sleep-sort. In case you're not familiar with that ridiculous algorithm, here it is in bash:

#!/bin/bash  function sort() {     for num in "$@" ; do         (         sleep $num         echo $num         ) &     done     wait }  sort 6 1 3 4 

Answer 2

I am fairly sure that the author of the comic is wrong. Below is a more formal analysis of the algorithm.

To begin with, we will need to set up some ground rules for how frogs eat flies. I will assume that all frogs can eat flies at constant rate r. That is, it takes r seconds for a frog to eat one fly, 10r seconds for a frog to eat ten flies, etc. Next, let's make the (reasonable) assumption that all the frogs are eating in parallel. We'll also assume that it takes j time for a frog to jump out of an empty box.

We also need to factor in setup time. Let's assume that we have on hand an unlimited supply of flies, frogs, and boxes, and let's say that it takes b time to get a box and y time to put a single fly into a box. Finally, we'll assume that it takes f time to put a frog into a box. For simplicity, we'll assume that the frogs don't start eating flies until we explicitly instruct them to, so that frogs placed into boxes before other frogs don't get a headstart.

One last detail - let's assume that it takes w time to write down a number.

In that case, the runtime of this algorithm is given as follows. Suppose that our list of numbers to sort is x₁, x₂, ..., x_n. In that case, the amount of time required to set up all the boxes will be n(b + f) + y(Σx_i). The reason for this is that we need to get n boxes and put one frog into each box (hence the first term), plus y units of time for each of the flies (hence the second term).

In the course of the algorithm, we will need to write down each number exactly once, when the frog jumps out of its box. This means that across the entire algorithm, we will do nw work writing down the sorted sequence.

Finally, we have to consider how long it takes for all frogs to finish. Since all the frogs are eating in parallel, all that we need to care about is the frog that has the most flies to eat. This frog will have x_max flies to eat, where x_max is the maximum number in the input list. Thus the time spent by the frogs in doing their eating is given by r x_max. Factoring in the jump taken by the final frog, the frogs, all working in parallel, will collectively finish in rx_max + j time.

This means that the overall time for the algorithm is given by

n(f + b) + yΣx_i + nw + rx_max + j.

If we now assume that "one unit of work" will suffice to do any of the individual operations (have a frog eat a fly, or jump out of a box, or to put a frog in a box, etc.), the total time required is at most

n + Σ(x_i) + x_max + 1

Noting that x_max ≤ Σx_i, we get that the overall runtime of this algorithm is Θ(n + Σx_i). In other words, the runtime is proportional to both the number of numbers to sort, and the total size of the numbers to be sorted.

Note that this runtime doesn't have any logarithms in it, so we immediately can conclude that the author's runtime analysis is incorrect.

Finally, note that this is a really bad sorting algorithm. The counting sort algorithm could sort n natural numbers in time O(n + U), where U is the maximum value to be sorted, which is asymptotically better than FrogSort. The radix sort algorithm could do this in O(n lg U) time, which is better for large values of U. Then again, both algorithms require sophisticated machinery, which probably wouldn't exist in the setting described by the comic.

Hope this helps!