Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>As a general rule, generating random input is not a good way to figure out worst-case running time. For example, quicksort runs in O(n log n) on average, but in the worst case it runs in O(n^2). However, even if you generated a huge number of random samples, for moderately large n you would never come anywhere close to the worst case. Instead, try and construct a worst-case input manually. </p> <p>In this case, it seems that the worst case, assuming that each array has length N, occurs if </p> <pre><code>L1 = (N,2N,2N+1,...,3N-3,3N) L2 = (N+1,N+2,...,2N-1,3N-1) L3 = (1,2,...,N-1,3N-2) </code></pre> <p>To see why, trace the execution of the algorithm. The first thing that happens is that the first N-1 elements of <code>L3</code> will get added to <code>L</code>. Each of these iterations of the loop will have 3 comparisons: two in the first <code>if</code> statement and one in the second. Note that we need <code>L1[1]&lt;L2[1]</code> otherwise it will skip the second comparison in the first <code>if</code></p> <p>Next will be the element <code>L[1]=N</code>, which takes one comparison only.</p> <p>After this come the first N-1 elements of <code>L[2]</code>, each of which will require two comparisons, one to <code>L1</code> and one to <code>L3</code>. </p> <p>Next come the next N-2 elements from <code>L1</code>, with one comparison each.</p> <p>At this point there is only one element left in each list. <code>L3</code> gets picked first, with 3 comparisons, and then one comparison for <code>L2</code>, and that's it.</p> <p>The total is </p> <pre><code>(N-1)*(3+2+1)+3+1 = 6N - 2 </code></pre> <p>I think this is the worst case, but you might be able to squeeze one more out of it somewhere. Also, I may have made a mistake, in which case somebody here will probably catch it. The next thing you should do is try to actually prove that this is the worst-case running time.</p> <p>PS This algorithm is not optimal for merging three lists. Picking the smallest element from the front of the three lists should only require 2 comparisons at most, not 3. If you find that <code>L2&lt;L1</code> and <code>L1&lt;L3</code> then it's not necessary to compare <code>L2</code> and <code>L3</code> since you already know that <code>L2</code> is smaller. </p> <p>On edit: it shouldn't be too hard to prove that this is actually the worst case. Assuming none of the lists are empty, the number of comparisons per iteration is:</p> <ul> <li>3 if L3 is smallest and L1 &lt; L2</li> <li>2 if L2 is smallest </li> <li>1 if L1 is smallest</li> </ul> <p>That right there gives you an upper bound of N*6, since each list can only be the smallest N times. So completing a proof just requires examining what happens at the end where the lists become empty.</p>
    singulars
    1. This table or related slice is empty.
    1. POCounting number of comparisons and analyzing the efficiency of a particular algorithm using programming and/or mathematics
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USmrip
    1. USmrip
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POCounting number of comparisons and analyzing the efficiency of a particular algorithm using programming and/or mathematics
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

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