Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I am fairly sure that the author of the comic is wrong. Below is a more formal analysis of the algorithm.</p> <p>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.</p> <p>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.</p> <p>One last detail - let's assume that it takes w time to write down a number.</p> <p>In that case, the runtime of this algorithm is given as follows. Suppose that our list of numbers to sort is x<sub>1</sub>, x<sub>2</sub>, ..., x<sub>n</sub>. In that case, the amount of time required to set up all the boxes will be n(b + f) + y(&Sigma;x<sub>i</sub>). 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).</p> <p>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.</p> <p>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<sub>max</sub> flies to eat, where x<sub>max</sub> is the maximum number in the input list. Thus the time spent by the frogs in doing their eating is given by r x<sub>max</sub>. Factoring in the jump taken by the final frog, the frogs, all working in parallel, will collectively finish in rx<sub>max</sub> + j time.</p> <p>This means that the overall time for the algorithm is given by</p> <blockquote> <p>n(f + b) + y&Sigma;x<sub>i</sub> + nw + rx<sub>max</sub> + j.</p> </blockquote> <p>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</p> <blockquote> <p>n + &Sigma;(x<sub>i</sub>) + x<sub>max</sub> + 1</p> </blockquote> <p>Noting that x<sub>max</sub> &le; &Sigma;x<sub>i</sub>, we get that the overall runtime of this algorithm is <strong>&Theta;(n + &Sigma;x<sub>i</sub>).</strong> 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.</p> <p>Note that this runtime doesn't have any logarithms in it, so we immediately can conclude that the author's runtime analysis is incorrect.</p> <p>Finally, note that this is a really bad sorting algorithm. The <a href="http://en.wikipedia.org/wiki/Counting_sort">counting sort</a> 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 <a href="http://en.wikipedia.org/wiki/Radix_sort">radix sort</a> 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.</p> <p>Hope this helps!</p>
    singulars
    1. This table or related slice is empty.
    1. POIs the analysis of FrogSort in Saturday Morning Breakfast Cereal correct?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. UStemplatetypedef
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COanother assumption is that the frogs are hungry and would eat at least n flies without stopping at rate r, for any useful value of n.
      singulars
      1. PO
      1. USarikb
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload