CSCD-255
2015-02-13


Loops and Timing

Time required for a program segment with a loop depends on the number of times the loop is executed.  The simplest case is the time required for the linear search of an array.  See 10 Feb.  While the time required to find something obviously varies from immediately (in x[0]) to n (in x[n-1]), it is also obvious that the time required to fail to find is n one must examine every entry.  Also we can say that the average time to find something scales as about n/2.  This is referred to a linear time, and is called O(n) order of n.  That means that if the size of the problem (n) doubles, the ratio of the times required also doubles by talking about the ratio, we cancel out the constant part of the time required.

Sorting gives us a nested loop.  Here is an implementation of the selection sort demonstration program from 12 Feb. with the "find index of largest" logic imbedded in the sort itself:
SelectionSort.txt   SelectionSort.c   SelectionSort.exe

The loop for (lim = n; lim > 1 ; ) executes n-1 times. For each value of lim the nested loop for (ck = 1; ck < lim; ck++) executes lim-1 times.  This ties into a famous formula:

The sum of all the integers from 1 up to n is given by n * (n+1) / 2.  Since we're talking about ratios we simplify this to O(n2) and call it quadratic complexity.

Here's a link to the story of Carl Gauss discovering this formula at an early age in the sum of the numbers from 1 to 100.

Finally, a simple example of nesting three loops:
Triple.txt   Triple.c   Triple.exe


Faster Finding in Arrays

We see that finding something in an array by examining individual cells required linear time.  But what if the array is sorted?

Let's look at a number guessing game, with only Goldilocks clues:  too low, too high, and just right.  This is a program from the Winter 2014 quarter.
numberGuess.txt   numberGuess.c   numberGuess.exe

The optimal strategy, in this case, is to always check in the middle of the known too-low and too-high values.

Please enter a number between 1 and 100 inclusive 50
Too High - You have 9 tries left
Please enter a number between 1 and 100 inclusive 25
Too High - You have 8 tries left
Please enter a number between 1 and 100 inclusive 12
Too Low - You have 7 tries left
Please enter a number between 1 and 100 inclusive 18
You Got it
Play again (y/n) n

If the array is sorted, then searching for a value can take advantage of this strategy:  each pass through the loop is guaranteed to discard half of the array segment being considered.

It is referred to (for obvious reasons) as binary search:

// Binary search.  x[] is presumed to be sorted.
int BinSrch (int x[], int n, int sought)
{
   int lo = 0, hi = n-1, mid;

// On average, 1 1/2 comparisons per loop iteration
   while (lo <= hi)     // Note return WITHIN the loop.
   {
      mid = (lo + hi) / 2;
      if (sought > x[mid])
         lo = mid + 1;
      else if (sought < x[mid])
         hi = mid - 1;
      else
         return mid;    // Early exit on success
   }

   return -1;           // Fail-to-find flag
}

Note:  in this demonstration implementation, there is the option of seeing every step of the binary search (if DEBUG has been #defined as non-zero).
BinSrch.txt   BinSrch.c   BinSrch.exe