# Complexity

Last translate with upstream: a032fb3

Time complexity and space complexity are important criteria to measure the efficiency of an algorithm.

## Count of Elementary Operations¶

An algorithm has different performances on different computers. It is hard to calculate the actual performance theoretically and is troublesome to measure it. Thus, it's more often for us to consider the count of elementary operations required by an algorithm rather than the actual time used.

For a typical computer, basic arithmetic, accessing or assignments to variables (of standard data types, the same below), can all be treated as elementary operations.

The count or estimation of elementary operations can be criteria when evaluating the efficiency of an algorithm.

## Time Complexity¶

To evaluate the performance of an algorithm, the data size is required to be taken the data size into consideration, which mostly referring to how many nodes, edges, or numbers are in the input. Generally, the larger the data size, the longer time the algorithm performs. But when we evaluate the performance in competitive programming, the most important is not its time cost in a specific size, but its growing trend as the data size grows, as known as **time complexity**.

The main reasons for considering in this way are listed below:

- Modern computers are capable of processing billions or more elemental operations, so the data size we need to process is usually enormous. For example, assume that algorithm A has a time cost of
100n n n^2 100 - We use the counts of elementary operations to represent the time cost of an algorithm. However, different kinds of elementary operations' time cost differs, for example, the time cost of addition and subtraction is far less than division. By ignoring the difference between different kinds and counts of operations when calculating time complexity, we can eliminate the impact of different time cost between operations.

Of course, the running time of an algorithm is not entirely determined by the input size, but is also correlated with the content of the input. Therefore, the time complexity is further divided into several categories. For example:

- Worst-case time complexity, referring to the input of maximum time complexity for each input size. In competitive programming, since the input can be given arbitrarily in given constraints, to ensure an algorithm can process any data in certain size in time, we generally consider the worst-case time complexity.
- Average-case time complexity, which is the average of the complexity on every possible inputs under constraints for each data size. (Or, the expected complexity on random input.)

As "the trend of time cost growing with data size's increasing" is an ambiguous concept, we need to represent the time complexity formally using **asymptotic notation** introduced below.

## Asymptotic Notation¶

Briefly, the asymptotic notation ignored the slower growing part of a function and its coefficient and constants, but preserved the important part showing the growing trend of this function.

### Θ-Notation¶

For functions

In other words, it means by saying

For example,

### Big O Notation¶

Θ-Notation both shows the upper and lower bound of a function. However, if we only know its asymptotical upper bound but not lower, we can use

It is more common to use big O notation while considering time complexity, as we are usually concerned with the upper bound of the program's time cost rather than the lower bound.

Note that the "upper" and "lower" bounds here are for the trend of the function, not for the algorithm, whose upper case refers to worst-case time complexity but not big O notation. Therefore, using Θ-notation is completely viable to represent worst-case time complexity, and it can even be said that Θ-notation is more accurate than big O notation. As for the main reason for using O notation more often, one is we sometimes can prove the upper bound, but not lower bound (this is usually the case for more complicated algorithm and analyzing its complexity), and the other reason is the character O is easier to input in a computer.

### Ω-Notation¶

Similarly, we use Ω-Notation to describe the asymptotical lower bound of a function. We say

### o-Notation¶

If

### ω-Notation¶

If

### Common Properties¶

f(n) = \Theta(g(n))\Leftrightarrow f(n)=O(g(n))\land f(n)=\Omega(g(n)) f_1(n) + f_2(n) = O(\max(f_1(n), f_2(n))) f_1(n) \times f_2(n) = O(f_1(n) \times f_2(n)) \forall a \neq 1, \log_a{n} = O(\log_2 n)

## Simple Examples of Calculating Time Complexity¶

### for-expression¶

```
// C++ Version
int n, m;
std::cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
for (int k = 0; k < m; ++k) {
std::cout << "hello world\n";
}
}
}
```

```
# Python Version
n = int(input())
m = int(input())
for i in range(0, n):
for j in range(0, n):
for k in range(0, m):
print("hello world")
```

The time complexity of the code above is

### DFS¶

While performing depth-first search (article not translated) on a graph with

## Identifying Constants¶

When we are going to perform several operations, how to determine whether these several operations will impact time complexity? e.g.:

```
// C++ Version
const int N = 100000;
for (int i = 0; i < N; ++i) {
std::cout << "hello world\n";
}
```

```
# Python Version
N = 100000
for i in range(0, N):
print("hello world")
```

If the value of

When calculating time complexity, it is important to figure out which variables should be treated as the size of data size. All other variables not relating to input data size will be treated as constants and treated as

## Master Theorem¶

By using master theorem we can quickly calculate the time complexity of a recursive algorithm.

Assume we have a recurrence relation formula,

Then,

## Amortized Complexity¶

Algorithms tend to modify data in memory, and multiple executions of an algorithm will have impact on each other by modifying data.

E.g., for the sorting-by-size operation in quicksort, the worst-case time complexity is seemed to be

The overall complexity of multiple operations divided by the number of operations is **Amortized Complexity**.

## Potential Method of Amortized Analysis¶

Potential method of amortized analysis is a method for finding the upper bound of amortized complexity. The key to finding amortized complexity is to represent the impact to current operation from previous operation.

Definition of *state*: *E.g., in quicksort, a "state" is an subscript interval needed to be sorted.*

Definition of *initial state*: *E.g., in quicksort, an "initial state" is the whole array.*

Assume

Let

Let

(It is obvious that positive and negative ones cancel)

And because

Therefore, if

Potential method have many tricks. Examples omitted here.

## Space Complexity¶

Similarly, the growing trend of space cost with input sizes' growth can be measured by **space complexity** using similar methods mentioned above.

## Calculate Complexity¶

The article mainly introduced complexity from the perspective of algorithm analysis. If interested you can visit Computational Complexity (not translated) for further reading.

buildLast update and/or translate time of this article，Check the history

editFound smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github

peopleContributor of this article linehk

translateTranslator of this article Visit the original article!

copyrightThe article is available underCC BY-SA 4.0 & SATA; additional terms may apply.