- This is an algorithm where the number of steps is directly proportional to the size of the data set, seen in line C on the Order of Algorithms graph. As N increases, the number of steps also increases.
public long sumData( ArrayList<Integer> list )
{
long total = 0;
Iterator<Integer> itr = list.iterator();
while( itr.hasNext() )
{
total += itr.next();
}
return total;
}
-
In the above example, as the size of the array increases, the number of steps increases at the same rate.
-
A non-recursive linear algorithm, O(N), always has a loop involved.
-
Recursive algorithms, in which the looping concept is developed through recursive calls, are usually linear. For example, the recursive factorial function is a linear function.
public long fact( int n )
{
// precondition: n > 0
if ( n == 1 )
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.
