Computational complexity theory

Computational complexity theory is a part of computer science. It looks at algorithms, and tries to say how many steps or how much memory a certain algorithm takes for a computer to do. Very often, algorithms that use fewer steps use more memory (or the other way round: if there is less memory available, it takes more steps to do). Many interesting algorithms take a number of steps that is dependent on the size of the problem.

Different classes of complexity

Constant Complexity

Complexity theory also looks at how a problem changes if it is done for more elements. A problem of constant complexity class is the only class in which this is not true. A problem with constant complexity takes the same number of steps to complete no matter the size of the input or the number of elements it is computed on. Broadcasting a message can be thought of as a problem of constant complexity. No matter how many people need to receive a message, all can listen on to one single broadcast with no extra broadcasts needed.

Linear complexity

Mowing the lawn can be thought of as a problem with linear complexity. Mowing an area that is double the size of the original takes twice as long.

Quadratic complexity

Suppose you want to know which of your friends know each other. You have to ask each pair of friends whether they know each other. If you have twice as many friends as someone else, you have to ask four times as many questions to figure out who everyone knows. Problems that take four times as long when the size of the problem doubles are said to have quadratic complexity.

Logarithmic complexity

This is often the complexity for problems that involve looking things up, like finding a word in a dictionary. If the dictionary is twice as big, it contains twice as many words as the original to compare to. Looking something up will take only one step more. The algorithm to do lookups is simple. The word in the middle of the dictionary will be either before or after the term that needs to be looked up, if the words do not match. If it is before, the term needs to be in the second half of the dictionary. If it is after the word, it needs to be in the first half. That way, the problem space is halved with every step, until the word or definition is found. This is generally known as logarithmic complexity

Exponential complexity

There are problems that grow very fast. One such problem is known as the Travelling salesman problem. A salesman needs to take a tour of a certain number of cities. Each city should only be visited once, the distance (or cost) of the travelling should be minimal, and the salesman should end up where he started. This problem has exponential complexity. There are n factorial possibilities to consider. Adding one city (from n to n+1) will multiply the number of possibilities by (n+1). Most of the interesting problems have this complexity.