Computational complexity

In computer science, computational complexity is about how much time and memory an algorithm needs to solve a problem. We look at how many steps a computer takes and how much space it needs to store information while running a program. This helps us know which programs work best for big jobs.

The complexity of a problem depends on the best way to solve it. Even if we find one good method, there might be an even better one. Scientists study both the ways to solve problems and the problems themselves to find the most efficient solutions.

Because the size of the job can change, complexity is often shown as a rule that connects the job size to the time or space needed. For example, a small task might be quick, but a huge task could take much longer. This helps computer experts choose the right method for different kinds of work.

Resources

When we think about how hard a computer job is, we look at how much time and memory it needs.

We don’t use real-time like seconds because computers change. Instead, we count the small steps a computer takes to finish a task. These steps are like tiny jobs the computer does one after another.

We also care about how much space a task needs in the computer’s memory. Some tasks need a lot of space. Others need only a little.

For tasks where many computers work together, we look at how much they need to share information. This is called communication complexity.

There are other ways to measure how hard a task is, like counting the math steps needed. Sometimes, these steps take longer if the numbers are very big!

Main article: circuit complexity

Main article: communication complexity

Complexity as a function of input size

We look at the time a computer needs to solve a problem. This idea also works for other things like memory space.

We can't test every possible input for a computer program. So, we talk about how hard a problem is based on the size of the input. This size is written as n (the number of bits in the input). Even for inputs of the same size, some can be easier or harder to solve. Here are two ways to talk about complexity:

• The worst-case complexity is the longest time it could ever take for any input of size n.
• The average-case complexity is the typical time it takes when you look at all possible inputs of size n.

When people just say “complexity,” they usually mean the worst-case time complexity.

Asymptotic complexity

Main article: Asymptotic computational complexity

It can be tricky to know exactly how much time or space an algorithm will need, especially for very large problems. Because of this, computer scientists often look at how the amount of time or space an algorithm needs grows when the problem gets bigger and bigger. They use something called "big O notation" to describe this growth.

For example, the usual way to multiply two big whole numbers takes about O(n²) time. This means that if you double the number of digits, the time it takes will go up by about four times. This helps us understand how well an algorithm will work when dealing with really large numbers.

Models of computation

The difficulty of a problem can change depending on the model of computation used. This model describes the basic steps taken in a set time. If the model is not mentioned, it is usually a multitape Turing machine, because many realistic models work in similar ways for most problems.

Deterministic models, such as recursive functions, lambda calculus, and Turing machines, follow steps that are fixed by the past state. Non-deterministic models, like non-deterministic Turing machines, allow some choices during calculations and look at the best results at the same time. This idea links to the important P = NP question, which wonders if problems solved quickly on a non-deterministic machine can also be solved quickly on a deterministic one.

Parallel and distributed computing divide tasks among many processors. Parallel computing makes data sharing faster, while distributed computing uses networks. The aim is to create algorithms where the total time multiplied by the number of processors is close to the time on one processor.

Quantum computing, based on quantum mechanics, might solve some problems faster, but building these computers is still mostly theoretical. Quantum complexity theory looks at problem difficulty for quantum computers and helps make post-quantum cryptography to guard against future quantum attacks.

Main articles: Parallel computing and Distributed computing

Problem complexity

The complexity of a problem is about how hard it is to solve using the best method. We usually compare this to how much time or memory a computer needs. For many problems, you need to look at all the information given, which takes time related to the amount of data.

Some problems are harder because the answers can be very big. For example, solving certain equations can sometimes need a lot of steps. Sorting items, like putting numbers in order, also needs a certain amount of steps to make sure everything is in the right place.

Use in algorithm design

It is important to know how much work an algorithm needs when we design it. This helps us know how fast it will run.

Some people think that as computers get faster, we don’t need to worry about this. But this is not true. Faster computers let us work with more data. For example, sorting a few hundred names can be done quickly by almost any method. But sorting a million names can take a long time if we use a slow method. Smart methods, like quicksort and merge sort, can do this job much faster than simpler ones.

Knowing how much work an algorithm needs helps us choose better ways to solve problems and improve methods without trying every option.