3. Complexity

To run an algorithm on a computer, you first have to convert it to source code. You can often implement an algorithm in many different ways. Some will be more efficient than others, using fewer steps to accomplish the same task.

The number of steps needed to carry out its task is a measure of the programs complexity. In general, you want your program to have as little complexity as possible, so it executes quickly.

Let's look at an example. This program prints out a set of numbers once the input (mynumber) is entered:

     mynumber = input("Enter your number")
     print("the value you entered is", mynumber)
     print("These are the numbers")
 
     for i = 1 to mynumber
       print "The value is:"
       print i
     next i 
     print "Program complete"

The first block of code has three instructions. Every time the program runs, each of these lines is carried out exactly once, for a total of three steps.

		Number of steps = 3

The next section is a loop. The loop contains four instructions, so every time it runs, the number of steps in the program increases by four.

		Number of steps = 3 + 4n

Where n is the value of the variable mynumber.

After the loop, there is one more line of code and so the final number of steps is

		3 + 4n + 1

Another programmer might write it differently and so the complexity of their version can also be evaluated, but they will not be able to alter the N dependency as that is inherent in the algorithm.

This is why Big O is so useful in assessing algorithms as it is largely independent of how it is implemented in code.

Once the expression is stated, the Big O expression can also be worked out - see next page