Section 3 - Big-Oh Estimations From Code

3A.3.1 Getting a Quick Big-Oh

All the math is nice to know, but it is much easier to use than it is to define. Here are a few down-and-dirty rules you can use to get a quick Big-Oh estimate.

First Simplifying Assumption: No Function Calls (or Function Calls Which Are Constant Time)

If we are analyzing some code that has no function calls in it (or the function calls are known to be constant time), then we can apply the following rules:

1. If you have no loops, then your algorithm is constant time.
2. Anything outside a loop can be ignored.
3. If you have one loop following another (i.e., not nested) only the longer loop counts.
4. If you have nested loops, compute from the inside out, multiplying times as you go.
5. If you have a loop whose upper limit (i.e., # of passes) does not depend on N, then the loop statement does not add anything to the estimate.
6. If you have a loop that does depend on N linearly (i.e., the for k = 1 to N or k = 0 to N/2 or k = 0.3* N down to 21) then it contributes a factor of N to the estimate.

These rules follow from the math we proved. For instance, rule 1 is the same thing as saying an algorithm which is O(c) for some constant c, is the same as O(1), because constant factors don't count. Rule 2 is the same thing as saying O(N + c) = O(N) because only the highest power of N counts. Therefore, an understanding of the mathematical rules will help you make decisions about algorithm counting, even if you forget these more specific counting rules.

Example 1: Insert

Here is an example, taken from our insert algorithm. I am going to count the time for one search; I will not show the outer, simulation, loop which was had nothing to do with a single insertion:

   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[writePosition].setArtist("Amerie");
   tunesArray[writePosition].setTitle("Outro");
   tunesArray[writePosition].setTime(63);

We see some function calls, but they are mutators, and thus constant time (they don't depend on N), so we can ignore them. Everything outside the loop can thus be ignored. There is no nesting, so that leaves the loop. Does the loop depend on N? Yes. The writePosition might be as low as 0 (worst case), and we are counting downward from arraySize, (which is our N). Therefore, the loop contributes a factor of N. That's the only contribution, so we see the algorithm is O(N).

This is typical - if you have a single loop, whose limit depends simply on N and no function calls, then you have an O(N) algorithm.

Second Simplifying Assumption: Counting Non-Recursive Function Calls

If we avoid recursion, we can incorporate function calls into the mix. If a function call is not constant time, then we simply incorporate its time estimate at that location in the algorithm and use it just as if it were a nested loop. For example if the time estimate of a function call is O(N), then that call contributes a factor of N in its position. It can be thought of as if it were a loop. In particular, if the function call occurs inside a loop, then its time estimate is multiplied by the loop estimate as we move "outward".

Example 2: Bubble Sort

Here is our bubble sort algorithm from Foothill_Sort.h. In this algorithm, N is arraySize.

template <typename Comparable>
void arraySort(Comparable array[], int arraySize)
{
    for (int k = 0; k < arraySize; k++)
       if (!floatLargestToTop(array, arraySize-1-k))
          return;
}
// returns true if a modification was made to the array
template <typename Comparable>
bool floatLargestToTop(Comparable data[], int top)
{
   bool changed = false;
   
   // notice we stop at length -2 because of expr. k+1 in loop
   for (int k =0; k < top; k++)
      if (data[k+1] < data[k] )
      {
         mySwap(data[k], data[k+1]);
         changed = true;
      }
   return changed;
}

template <typename Comparable>
void mySwap(Comparable &a, Comparable &b)
{
   Comparable temp;

   temp = a;
   a = b;
   b = temp;
}
 

floatLargestToTop() has two cases inside an if, but they both contain the same number of loops and function calls (the other stuff doesn't count) so they are equivalent. We can use either one to do our computation. It calls only compareTo() which is a constant time algorithm (the size of the String is not changing, if you are worried about that). So compareTo() can be ignored. Other than that, floatLargestToTop() contains a loop whose limit does depend on N. Why? Because it loops up to top, and top could be -- worst case -- array.length - 1, i.e., N - 1 which depends on N. So this method has a single loop and is therefore O(N).

Now back to the top-level function, arraySort(). We determined that the call to floatLargestToTop() counts for an N, and this is inside a loop that happens N times. Thus, we multiply N×N to get N². This completes the analysis: the algorithm. We have found that it is O(N²).

3A.3.2 Two Input Variables

We can do the same analysis with two inputs, N and M. In the case of our insertion program we actually did have two variables. N, the size of the array, and M, the number of simulations. Our analysis above was done assuming M was 1, but in our earlier program it was not. If you look back, you'll see that we had nested loops, and the outer loop was depending on one variable, M, while the inner was dependant on the other, N.

   // 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[writePosition].setArtist("Amerie");
      tunesArray[writePosition].setTitle("Outro");
      tunesArray[writePosition].setTime(63);
   }

Working from inside out, we get a factor of N from the inner loop and a factor of M from the outer loop. We still use the same basic rules, and multiply the two, even though N and M are different. Therefore, the algorithm that simulates M insertions in a list of N items is O(NM).