Skip to main content
Lesson 24 - Order of Algorithms
ZIPPDF (letter)
Lesson MenuPreviousNext
  
Quadratic Algorithms, O(N2) page 8 of 11

  1. This is an algorithm where the number of steps required to solve a problem increases as a function of N2. For example, here is bubbleSort.

    void bubbleSort (int[][] list)
    {
      for (int outer = 0; outer < list.length - 1; outer++)
      {
        for (int inner = 0; inner <= list.length - outer; inner++)
        {
          if (list[inner] > list[inner + 1])
          {
            // swap list[inner] & list[inner + 1]
            int temp = list[inner];
            list[inner] = list[inner + 1]);
            list[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 if statement is going to happen approximately N2 times.

  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:

    # if statements = (Outer loop) * (Inner loop)
    # if statements = (N) * (N/2)
    # if statements = N2/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.


Lesson MenuPreviousNext
Contact
 ©ICT 2003, All Rights Reserved.