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