Quadratic Algorithms, O(N^2)

1. This is an algorithm, seen in line E on the Order of Algorithms graph, in which the number of steps required to solve a problem increases as a function of N². For example, here is bubbleSort.

   void bubbleSort(ArrayList <Comparable> list){
       for (int outer = 0; outer < list.length - 1; outer++){
           for (int inner = 0; inner < list.size()-outer-1; inner++){
               if (list.get(inner).compareTo(list.get(inner + 1) > 0){
                   //swap list[inner] & list[inner+1]
                   Comparable temp = list.get(inner);
                   list.set(inner, list.get(inner + 1));
                   list.set(inner + 1, temp);
               }
           }
       }
   }
   

2. The if statement is buried inside nested loops, each of which is tied to the size of the data set, N. The statement is going to be executed approximately N times for each of N items, or N² times in all.

3. The efficiency of this bubble sort was slightly improved by having the inner loop decrease, but we still categorize this as a quadratic algorithm.

4. For example, the number of times the inner loop happens varies from 1 to (N-1). On average, the inner loop occurs (N/2) times.

5. The outer loop happens (N-1) times, or rounded off N times.

6. The number of times the if statement is executed is equal to this expression:

   Number of if statements = (Outer loop) * (Inner loop)
   Number of if statements = (N) * (N/2)
   Number of if statements = N²/2

7. The coefficient 1/2 becomes insignificant for large values of N, so we have an algorithm that is quadratic in nature.

8. When determining the order of an algorithm, we are only concerned with its category, not a detailed analysis of the number of steps.