Section 7 - Analysis

1A.7.1 Some Pencil Pushing

I advertised that we were going to go beyond just writing code - we will do some analysis. Without any tools yet to help us, let's ask, and attempt to answer, a question about our previous results. There are many numbers to compare, but I'm interested in this one at the moment. How come sorting 79 iTunesEntry objects seemed to take about the same time as inserting 500 such objects into the list? (In the previous page, both were so fast they each showed up as 0. But below, I'm giving you figures for an older computer on which I reran both experiments. You can try it on yours to see if you get similar results):

The insertion:

   Doing 500 insertions in array having 79 iTunes.

   Algorithm Elapsed Time: 0.0011 seconds.

The sort:

  Algorithm Elapsed Time: 0.0011 seconds.

The analysis we'll do is partly for fun and partly to get our brains moving. It is not a rigorous one. You won't be tested on it. But it does ring of common sense, an essential tool for us.

1A.7.2 A loceffOp

We don't know how much an operation costs in my computer, and I can't find it. But let's call the length of time of an assignment statement, like a = b, one loceffOp. Furthermore, let's assume that a comparison and a function call each takes one loceffOp.

1A.7.3 Bubble Sort

At the top level, our (slow but easy) bubble sort algorithm looks like this:

template <typename Comparable>
void arraySort(Comparable array[], int arraySize)
{
    for (int k = 0; k < arraySize; k++)
       if (!floatLargestToTop(array, arraySize - 1 - k))
          return;
}

arraySize is 79, so we are executing a loop that has 79 comparisons and 79 function calls. 158 loceffOps. (I'm not going to count the k++ or the if (!...) since I assume they are very fast, and we'll take a comparable shortcut when calculating the competing algorithm.)

However, as we know from studying the bubble sort, we won't usually run the loop the full 79 times. The if statement tells us that once we detect a sorted list, we return. In fact, I checked, and the list was sorted after 70 loop passes, so in reality, this was only 70 + 70 = 140 loceffOps.

Now we look inside the floatLargestToTop() method

template <typename Comparable>
bool floatLargestToTop(Comparable data[], int top)
{
   bool changed = false;
   
   // we stop at top-1 = (worst case) arraySize-2 due to k+1 in loop
   for (int k = 0; k < top; k++)
      if ( !(data[k] < data[k+1]) )
      {
         mySwap(data[k], data[k+1]);
         changed = true;
      }
   return changed;
}

This gets called, by my previous assumption slightly less that the full 79 times - it will only be called 70 times. The first time it is called, top will be 78 and the last time, top will be 9 (it so happens due to the specific array passed in, which is typical). So, in an average call, top is (78 + 9)/2 = 44 (I'll do a lot of rounding here). That means the loop inside this program has 44 passes. I'll ignore the initialization of changed = false since it probably is part of function call overhead. Counting the k < top comparison 44 times, that's 44 loceffOps. Inside each loop we do another comparison, data[k] < data[k+1], which is an additional 44 loceffOps. But that comparison is really a function call (typically < is an overloaded operator), and if you were to look inside iTunesEntry.cpp you would see that this involves a switch and another compare (usually), which adds to 2 more operations done 44 times. We are now at 132 loceffOps. If the comparison is true, we call mySwap(). There is a 1 loceffOp for the function call mySwap() and 3 loceffOps inside mySwap() for the assignments (you all know that a swap is three assignments - I hope.). Then we add the changed = true assignment to bring the tally to 5 loceffOps, but only when the if test is true. Let's say it's true half the time, so that 22 times through the loop, we have 5 additional loceffOps. So floatLargestToTop() is costing us, on average, 22*5 + 132 = 242 loceffOps. Call it 250.

Putting this all together, we have 140 loceffOps at the top level, and for the 70 floatLargestToTop() function calls we have an additional 250, resulting in a grand total of 140 + 70*250 = 17,640 loceffOps. Call it 18,000.

Whew. That exercised a few brain cells, and what fun.

1A.7.4 Insertion

Next we count the cost of the insertion algorithm. Here it is:

 // we will do NUM_INSERTIONS insertions, throwing away tunes that run off the top
   for (int attempt = 0; attempt < NUM_INSERTIONS; attempt++)
   {
      writePosition = somePositions[ attempt % NUM_POSITIONS ];

      // move everything up one 
      for (int k = arraySize; k > writePosition; k--)
         tunesArray[k] = tunesArray[k-1];

      // now put a new tune into the free position
      tunesArray[write_position].setArtist("Amerie");
      tunesArray[write_position].setTitle("Outro");
      tunesArray[write_position].setTime(63);
   }

First we count the main loop bookkeeping. We are doing 500 insertions which means 500 loceffOps for the loop comparison. We'll add this to what we get for the interior of the loop in our next computation.

Next we look inside the main loop without counting the inner loop, which we'll count in a moment. We'll call the assignment of the write_position 1 loceffOp (we didn't count the k+1 in the sort, so we won't count the % here). Skipping the inner loop for now, we move to the last three lines where we assign the data for the inserted object. They account for 3 method calls which, internally, do some sort of test and an assignment, so we'll call it 3 loceffOps per call times 3 calls, for a total of 9 loceffOps. So, except for the inner loop, we have 1 + 9 = 10 loceffOps per main loop pass. That's 500 * 10 = 5000 loceffOps inside the loop. We have to add the main loop bookkeeping (500) which takes us to 5000 + 500 = 5500.

Now for the inner loop. Sometimes we will insert near the front of the list, sometimes near the end. We'll take the middle position: 79 / 2 = 38 as typical. So this loop happens 79 - 39 = 40 times. For each pass we do 1 comparison and 1 assignment. That's 2 loceffOps. So the inner loop costs us 40 * 2 = 80 loceffOps.

The inner loop is done 500 times, which then costs 500*80 = 40,000 loceffOps.

The grand total for the insertion test is 40,000 + 5500 = 45,500 loceffOps. We'll round to 45,000.

1A.7.5 The Comparison

The sort cost 18,000 loceffOps and the insertion cost about 45,000 loceffOps. What do we conclude from all this? When we compare two code fragments we are looking for orders of magnitude differences. The difference between .015 and .15 seconds is an order of magnitude difference: one is 10x as long (large, time consuming) as the other. Here we have one estimate less than thrice the other. This is no order of magnitude difference here, so we don't expect to see the running times to vary significantly -- and they don't.

There is no guarantee that my assumptions were accurate. The point here is that if we were to replace these assumptions with more accurate ones, chances are, we'd still find that the two calculated times were of the same order of magnitude - one might be twice the other -- that's the same for our purposes.

Do not misinterpret the conclusion. It does not say that a sort is just as expensive or cheap as an insertion. It is a comparison between one sort on 79 items and 500 insertions in a list of the same 79 items. If anything, we will conclude that the insertion is much cheaper, because we can do 500 of them in about the same time as we did one sort. All we did was compare an absolute time of two procedures, so we were not comparing the cost of the algorithms, but the cost of the program runs.

Another thing we did not do here is to measure how the algorithms grow as the number of items -- 79 in this case -- grows. When we change 79 to 790, how will the results change? This is an even more important question, and one that we will answer in two weeks. The only thing we care about today is that we can measure some specific program running times using a primitive, but logical, technique of counting up computer operations.

We will try to avoid messy and guessy estimates like this one, but it doesn't hurt to do one now at the beginning of the class, to get a feel for the process. We see that we can actually get some reasonable answers even with very crude assumptions.