| |
Linear Algorithms, O(N) | page 6 of 11 |
This is an algorithm where the number of steps is directly proportional to the size of the data set. As N increases, the number of steps also increases.
long sumData (int[] list)
// sums all the values in the array
{
long total = 0;
for (int loop = 0; loop < list.length; loop++)
{
total += list[loop];
}
return total;
}
In the above example, as the size of the array increases, so the number of steps increases at the same rate.
A non-recursive linear algorithm, O(N), always has a loop involved.
Recursive algorithms are usually linear where the looping concept is developed through recursive calls. The recursive factorial function is a linear function.
long fact (int n)
// precondition: n > 0
{
if (1 == n)
return 1;
else
return n * fact(n - 1);
}
The number of calls of fact will be n . Inside of the function is one basic step, an if /else . So we are executing one statement n times.
|