Algorithms
Introduction

A major portion of computer science is the study of algorithms. What are algorithms? An algorithm is a step by step solution to a problem. I could go into the formal definition of what an algorithm is but I won't. For the purposes of this page, what I have stated is sufficient.

So, just what kind of problems do algorithms solve? In genral, algorithms solve problems that can be solved in finite time. These problems include but are not limited to searching, sorting, numerical calculations, virtual memory/page replacement, CPU scheduling, and the list goes on.

Consider the problem of multiplying two numbers. There is an algorithm for solving such a problem and it is the way most of us have been taught to multiply. It usually involves multiplying digits and propigating carries, etc. Let me present an alternative method of multiplication. I've mixed language syntax but the idea is what is important. Not proper compilation.

Multiply(x,y)
begin
  z:=0;
  for i:=1 to x
    z:=z + y;
  return z;
end;

This actually performs multiplication as it is DEFINED. Remember, x*y is really x + x + ... + x repeated y times. However, for large numbers this process is not very efficient.

Complexity

The previous example illustrates an important principle. Just because we have found a solution to a problem does not always mean that it is the best solution. An algorithm's performance is often measured by its complexity. Complexity refers to how the number of basic operations the algorithm performs as input size increases.

For the mulitplication algorithm as stated above, we can count the number of additions performed. If we let x = n (we often refer to n as the size of our input) then n additions are performed. More than that, we refer to the complexity of this algorithm as O(n).