What is Computational complexity theory?
'''Computational complexity theory''' is a part of [[computer science]]. It looks at [[algorithm]]s, 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 aft