2. Scalability - Complexity

Algorithms run by computers are called 'programs'. Non-computer algorithms are often called 'protocols'.

Programs comprise a list of instructions. For example, here is a bit of source code to print the first ten natural numbers:

             For x = 1 to 10

               print x

             Next x

This is a fairly simple program. It's also very efficient at its task. But how do you measure something as abstract as 'efficiency'?

There are two main measures:

1. The time it takes for the algorithm to complete
2. The resources the algorithm needs. This is usually computer memory, i.e. 'space'.

These are important individually, but it's also important to note how they relate to one another. For example, what if you wanted to run an algorithm on a much larger data set? Does the time needed for completion increase slowly, or quickly?

This factor is called scalability, or complexity.

In this context, complexity means 'if input N increases, how much longer does it take to complete (time complexity) and how many more resources does it need (space complexity).