Linear Algorithms, O(N)

1. 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;
   }
   

2. In the above example, as the size of the array increases, 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, 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 (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.