Skip to main content
Lesson 24 - Order of Algorithms
Lesson MenuPreviousNext
  
Order of Algorithms page 3 of 11

  1. The order of an algorithm is based on the number of steps that it takes to complete a task. Time is not a valid measuring stick because computers have different processing speeds. We want a method of comparing algorithms that is independent of computing environment and microprocessor speeds.

  2. Most algorithms solve problems involving an amount of data, N. The order of algorithms will be expressed as a function of N, the size of the data set.

  3. The following chart summarizes the numerical relationships of common functions of N.

    ABCDE
    NO(log2N)O(N)O(N*log2N)O(N2)
    10101
    21224
    424816
    8382464
    1641664256
    325321601024
    646643844096
    128712889616384
    2568256204865536
    51295124608262144
    1024101024102401048576

    1. The first column, N, is the number of items in a data set.

    2. The other four columns are mathematical functions based on the size of N. In computer science, we write this with a capital O (order) instead of the traditional F (function) of mathematics. This type of notation is the order of an algorithm, or Big O notation.

    3. The graph below gives a clearer sense of the relationships among the columns of numbers. Since the vertical axis represents the theoretical number of steps required by an algorithm to sort a list of N items, lines B and C represent more efficient algorithms than D and E. Today's data sets can grow to enormous sizes, so algorithm designers are always looking for ways to reduce the number of steps, even on the fastest supercomputers.



    4. You have already seen column E in an experimental sense when you counted the number of steps in the quadratic sorting algorithms. The relationship between columns A and E is quadratic - as the value of N increases, the other column increases as a function of N2. The graph of column E is a portion of a parabola.


Lesson MenuPreviousNext
Contact
 ©ICT 2003, All Rights Reserved.