# 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.