Taking Longer Than Expected to Execute in C programming

Taking Longer Than Expected to Execute

In some instances, you might discover that your program is not completely “locked up” but is merely taking
longer than expected to execute. This situation can be frustrating, especially if you are working on a very fast
computer that can perform incredibly complex tasks in minuscule amounts of time. Following are some

program fragments that might take longer to execute than you would expect:
/*
* A subroutine to calculate Fibonacci numbers
*/
int fib( int i )
{
if ( i < 3 )
return 1;
else
return fib( i - 1 ) + fib( i - 2 );
}

A Fibonacci number is the sum of the two Fibonacci numbers that precede it, with the exception of one and
two, which are set to zero. Fibonacci numbers are mathematically very interesting and have many practical
applications.

NOTE
An example of a Fibonacci number can be seen in a sunflower. A sunflower has two spirals of seeds,
one of 21 seeds and one of 34 seeds. These are adjacent Fibonacci numbers.

On the face of it, the preceding code fragment is a very simple expression of the definition of Fibonacci
numbers. It seems, because of its minuscule length and simplicity, that it should take very little time to
execute. In reality, waiting for the computer to discover the Fibonacci value for a relatively small value, such
as 100, could leave one ready to collect Social Security. The following text will examine why this is so. Say that you want to compute the Fibonacci value for the number 40. The routine sums the Fibonacci values for 39 and 38. It has to compute these values as well, so for each of these two numbers, the routine must sum
two subvalues. So, for the first step, there are two subproblems, for the next step, there are four, next, eight.
The result of all of this is that an exponential number of steps end up being performed. For example, in the
process of computing the Fibonacci value for the number 40, the fib() function is called more than 200 million times! Even on a relatively fast computer, this process could take several minutes.Another problem that might take an unexpectedly long time to solve is the sorting of numbers:
/*
* Routine to sort an array of integers.
* Takes two parameters:
* ar -- The array of numbers to be sorted, and
* size -- the size of the array.
*/
void sort( int ar[] , int size )
{
int i,j;
for( i = 0 ; i < size - 1 ; ++ i )
{
for( j = 0 ; j < size - 1 ; ++ j )
{
if ( ar[ j ] > ar[ j + 1 ] )
{
int temp;

temp = ar[ j ];
ar[ j ] = ar[ j + 1 ];
ar[ j + 1 ] = temp;
}
}
}
}

Upon testing this code with several short lists of numbers, you might be quite pleased; it will sort short lists
of numbers very well and very quickly. But if you put it into a program and give it a very large list of numbers,
the program might seem to freeze. In any case, it will take a long time to execute. Why is that?
For the answer, look at the nested for loops. There are two loops, one inside the other, both of them with
the range of 0 to size - 1. This translates to the code inside of both loops being executed size*size, or size
squared times ! This code will perform acceptably on lists of 10 items; 10 squared is only 100. If, however,
you try to sort a list of 5000 items, the code in the loop is executing 25 million times. And if you try to sort
a list of one million numbers, which is not very uncommon in computer science, the code in the loop will
be executed one trillion times.

In either of these cases, you need to be able to accurately assess how much work the code is actually doing.
This assessment falls into the realm of algorithmic analysis, which is important for every programmer to
know.