Skip to main content
Lesson 24 - Order of Algorithms
Lesson MenuPreviousNext
  
Linear Algorithms, O(N) page 6 of 11

  1. 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;
    }
  2. In the above example, as the size of the array increases, so the number of steps increases at the same rate.

  3. A non-recursive linear algorithm, O(N), always has a loop involved.

  4. 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.


Lesson MenuPreviousNext
Contact
 ©ICT 2003, All Rights Reserved.