Computational complexity is a formal (mathematical) study of resource usage (usually time and memory) by computers as they're solving various types of problems. For example when using computers to sort arrays of numbers, computational complexity can tell us which algorithm will be fastest as the size of the array grows, which one will require least amount of memory (RAM) and even what's generally the fastest way in which this can be done. While time ("speed", number of steps) and memory (also space) are generally the resources we are most interested in, other can be considered too, e.g. network or power usage. Complexity theory is extremely important and one of the most essential topics in computer science; it is also immensely practically important as it helps us optimize our programs, it teaches us useful things such as that we can trade time and space complexity (i.e. make program run faster on detriment of memory and vice versa) etc.
Firstly we have to distinguish between two basic kinds of complexity:
Let us now focus on algorithm complexity, as problem complexity follows from it. OK, so what really is the "algorithm complexity"? Given resource R -- let's consider e.g. time, or the number of steps the algorithm needs to finish solving a problem -- let's say that complexity of a specific algorithm is a function f(N) where N is the size of input data (for example length of the array to be sorted), which returns the amount of the resource (here number of steps of the algorithm). However we face issues here, most importantly that the number of steps may not only depend on the size of input data but also the data itself (e.g. with sorting it may take shorter time to sort and already sorted array) and on the computer we use (for example some computers may be unable to perform multiplication natively and will emulate it with SEVERAL additions, increasing the number of steps), and also the exact complexity function will be pretty messy (it likely won't be a nice smooth function but rather something that jumps around a bit). So this kind of sucks. We have to make several steps to get a nice, usable theory.
The solution to above issues will be achieved in several steps.
FIRSTLY let's make it more clear what f(N) returns exactly -- when computing algorithm complexity we will always be interested in one of the following:
This just deals with the fact that some algorithms may perform vastly different for different data -- imagine e.g. linear searching of a specific value in a list; if the searched value is always at the beginning, the algorithm always performs just one step, no matter how long the list is, on the other hand if the searched value is at the end, the number of steps will increase with the list size. So when analyzing an algorithm we always specify which kind of case we are analyzing (WATCH OUT: do not confuse these cases with differences between big O, big Omega and big Theta defined below). So let's say from now on we'll be implicitly examining worst case scenarios.
SECONDLY rather than being interested in PRECISE complexity functions we will rather focus on so called asymptotic complexity -- this kind of complexity is only concerned with how fast the resource usage generally GROWS as the size of input data approaches big values (infinity). So again, taking the example of array sorting, we don't really need to know exactly how many steps we will need to sort any given array, but rather how the time needed to sort bigger and bigger arrays will grow. This is also aligned with practice in another way: we don't really care how fast our program will be for small amount of data, it doesn't matter if it takes 1 or 2 microseconds to sort a small array, but we want to know how our program will scale -- if we have 10 TB of data, will it take 10 minutes or half a year to sort? If this data doubles in size, will the sorting time also double or will it increase 1000 times? This kind of complexity also no longer depends on what machine we use, the rate of growth will be the same on fast and slow machine alike, so we can conveniently just consider some standardized computer such as Turing machine to mathematically study complexity of algorithms.
Rather than exact value of resource usage (such as exact number of steps or exact number of bytes in RAM) asymptotic complexity tells us a class into which our complexity falls. These classes are given by mathematical functions that grow as fast as our complexity function. So basically we get kind of "tiers", like constant, linear, logarithmic, quadratic etc., and our complexity simply falls under one of them. Some common complexity classes, from "best" to "worst", are following (note this isn't an exhaustive list):
Now we just put all the above together, introduce some formalization and notation that computer scientists use to express algorithm complexity, you will see it anywhere where this is discussed. There are the following:
Please note that big O/Omega/Theta are a different thing than analyzing best/worst/average case! We can compute big O, big Omega and big Theta for all best, worst and average case, getting 9 different "complexities".
Now notice (also check by the formal definitions) that we simply don't care about additive and multiplicative constants and we also don't care about some initial oscillations of the complexity function -- it doesn't matter if the complexity function is f(x) = x or f(x) = 100000000 + 100000000 * x, it still falls under linear complexity! If we have algorithm A and B and A has better complexity, A doesn't necessarily ALWAYS perform better, it's just that as we scale our data size to very high values, A will prevail in the end.
Another thing we have to clear up: what does input size really mean? I.e. what exactly is the N in f(N)? We've said that e.g. with array sorting we saw N as the length of the array to be sorted, but there are several things to additionally talk about. Firstly it usually doesn't matter if we measure the size of input in bits, bytes or number of items -- note that as we're now dealing with asymptotic complexity, i.e. only growth rate towards infinity, we'll get the same complexity class no matter the units (e.g. a linear growth will always be linear, no matter if our x axis measures meters or centimeters or light years). SECONDLY however it sometimes DOES matter how we define the input size, take e.g. an algorithm that takes a square image with resolution R * R on the input, iterates over all pixels and find the brightest one; now we can define the input size either as the total number of pixels of the image (i.e. N = R * R) OR the length of the image side (i.e. N = R) -- with the former definition we conclude the algorithm to have linear time complexity (for N input pixels the algorithm makes roughly N steps), with the latter definition we get QUADRATIC time complexity (for image with side length N the algorithm makes roughly N * N steps). What now, how to solve this? Well, this isn't such an issue -- we can define the input size however we want, we just have to stay consistent so that we are able to compare different algorithms (i.e. it holds that if algorithm A has better complexity than algorithm B, it will stay so under whatever definition of input size we set), AND when mentioning complexity of some algorithm we should mention how we define the input size so as to prevent confusion.
With memory complexity we encounter a similar issue -- we may define memory consumption either as an EXTRA memory or TOTAL memory that includes the memory storing the input data. For example with array sorting if an algorithm works in situ (in place, needing no extra memory), considering the former we conclude memory complexity to be constant (extra memory needed doesn't depend on size of input array), considering the latter we conclude the memory complexity to be linear (total memory needed grows linearly with the size of input array). The same thing as above holds: whatever definition we choose, we should just mention which one we chose and stay consistent in using it.
See also P vs NP.
As said, problem complexity is tied to algorithm complexity; a complexity of specific problem (e.g. sorting an array, factorization of a number, searching a sorted list etc.) is determined by the best possible algorithm that solves the problem (best in terms of analyzed complexity). Traditionally we use Turing machines and formal languages to analyze problem complexity. Here we'll stay a bit informal and only mention some ideas.
Similarly to algorithm complexity, with problems we again define classes that are only about "how quickly the resource usage grows as we increase input size". The main difference is we are examining problems, so the classes we get are classes of PROBLEMS (usually classes of formal languages, like e.g. in Chomsky's language hierarchy), not classes of functions (seen in algorithm complexity). Some common classes are:
Practically analyzing time complexity of algorithms mostly involves looking at the loops in our algorithm as these are what makes number of steps in algorithm variable. Linear sequences of instructions (such as initializations) don't interest us, no matter how long, as these have no effect on asymptotic complexity. But remember that looping may also be achieved with recursion etc., so just look carefully.
Let's consider the simple bubble sort array sorting algorithm, with the simple optimization that ends as soon as the array is sorted; here it is written in C:
void bubbleSort(int *array)
{
for (int i = 0; i < N - 1; ++i)
{
int end = 1;
for (int j = 0; j < N - 1 - i; ++j)
if (a[j] > a[j + 1])
{
swap(&a[j],&a[j + 1]);
end = 0;
}
if (end) // no swap happened => sorted, end
break;
}
}
The size of input data is the length of input array (N), for memory we consider only the extra memory used. Let's see about different complexities now:
if (end)) never triggers and so both loops (outer and inner one) in our algorithm run all their iterations; the outer loop is performed approximately N times (actually N - 1 times but remember that asymptotic complexity ignores -1 here as an additive constant) and for each of its iterations the inner loop runs approximately N - i times. So e.g. for N = 5 we get approximately 5 + 4 + 3 + 2 + 1 steps, so for given N we basically have to sum up numbers from 1 to N -- there is a formula for computing such sum and that is *(N (N + 1)) / 2 = N^2 / 2 + N / 2. With asymptotic complexity we just take the biggest term and ignore any multiplication constant (division by two), so we just see N^2 here and conclude that the time complexity of worst case for bubble sort is quadratic, i.e. O(N^2). Notice that technically we can also say the complexity belongs to any "worse" class, e.g. O(N^3) (as O(N^2) is its subclass), which is technically true but doesn't tell us as much. So here it's better to further more precisely say the complexity of worst case also belongs to Omega(N^2) (the lower bound) and therefore (by belonging to both O(N^2) and Omega(N^2)) also belongs to Theta(N^2), i.e. it "won't be slower BUT NOR faster than N^2".TODO: also something simpler? problem complexity?
Powered by nothing. All content available under CC0 1.0 (public domain). Send comments and corrections to drummyfish at disroot dot org.