Tutorial about time and memory complexity

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3904
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3494
8	Um_nik	3396
9	gamegame	3386
10	maroonrk	3350

№	Пользователь	Вклад
1	maomao90	164
1	cry	164
3	Um_nik	163
4	atcoder_official	159
5	awoo	158
6	adamant	157
7	-is-this-fft-	156
8	nor	154
9	TheScrasse	153
10	Dominater069	152

Motivation

I saw that many begginers don't really understand how to compute complexity and make lots of some mistakes in calculations. Even more skilled programers can have mistakes in this topic. I will write more intuitive way to understant time and memory complexity and this will be the main focus of this blog. There will also be more formal way, but in the spoiler.

What is complexity

In simple words, complexity is just number of operations that the program make. For example, if you have a cycle from 1 to 1000 with step 1, it is 1000 operations and if there you make one addition and one multiplication, it is already 3000 (since you make this two operations 1000 times). For memory it works in the same way. If you make an array of 100 elements, it has memory complexity 100. But in fact, it is hard to calculate complexities up to 1 in general case, while it is also not really needed, since compute makes 1 operation really fast. In the same way, 10 operations or 1000 operations. In fact, when we calculate complexities we do not look at constant. It means, that n operations (where n is some variable and has some numeric value) same as 2*n operations, or n+100 operations is same as n operations. That is same as when we made 1647859 operation, we can just say that we made $$$10^6$$$ operations which is more easier to work with. The reason for it is that it is easier to calculate complexities, since you do not need to look for each operation. Also, since programs use variables which have some range, we will use variables as well.

Types of compexitites

$$$O$$$. This notation is used when we want to tell that our program make at most this complexity. It means, that if your program have one loop which takes n operations, it has complexity $$$O(n)$$$, but also has complexity $$$O(n^2)$$$. So, if we say that reall number of operations that program makes will be a and number of operations that complexity says is b, then $$$a\le b$$$.
$$$o$$$. This notation is used when we want to tell that our program make less then this complexity. It means, that if your program have one loop which takes n operations, it can have complexity $$$o(n^2)$$$, but also can have complexity $$$O(n^9)$$$. So, if we say that reall number of operations that program makes will be a and number of operations that complexity says is b, then $$$a<b$$$.
$$$\Theta$$$. This notation is used when we want to tell that our program make same number of operations as this complexity. It means, that if your program have one loop which takes n operations, it has complexity $$$\Theta (n)$$$. So, if we say that reall number of operations that program makes will be a and number of operations that complexity says is b, then $$$a=b$$$.
$$$\Omega$$$. This notation is used when we want to tell that our program make at least the same number of operations as complexity. It means, that if your program have one loop which takes n operations, it has complexity $$$\Omega (n)$$$ or it is also $$$\Omega (1)$$$. So, if we say that reall number of operations that program makes will be a and number of operations that complexity says is b, then $$$a\ge b$$$.
$$$\omega$$$. This notation is used when we want to tell that our program make more operations then complexity. It means, that if your program have one loop which takes n operations, it has complexity $$$\omega (1)$$$ or it is also $$$\omega (log(n))$$$, but not $$$\omega(n)$$$. So, if we say that reall number of operations that program makes will be a and number of operations that complexity says is b, then $$$a> b$$$.

Formal definition (not needed for understanding)

In the remaining blog I will use only big O notation, since it is, in my opinion, the most important and popular.

Evaluating complexities

There are some rules for evaluating complexities and here are some of them:

$$$O(C)=O(1)$$$ for constant C and variables x and y.
$$$O(x)+O(C)=O(x)$$$ for constant C and variables x and y.
$$$O(x)+O(y)=O(x+y)=O(max(x,y))$$$ for variables x and y.
$$$O(x)\cdot O(y)=O(x\cdot y)$$$ for variables x and y.
$$$O(x)+O(x)=O(x)$$$ for variable x.

Example 1

1.  #include <bits/stdc++.h>
2.  using namespace std;
3.  
4.  int main(){
5.      int n,k;
6.      cin>>n>>k;
7.      int a[n];
8.      for(int i=0;i<n;i++){
9.          cin>>a[i];
10.     }
11.     for(int i=n-k;i<n;i++){
12.         cout<<a[i]<<" ";
13.     }
14.     return 0;
15. }

This code takes an array and output lask k elements of the array. The first number is just number of code line, to easier talk about the code. Note, that we assume that input and output works in $$$O(1)$$$.

First of all, we can assume that including library (1 line), using namespaces (2 line), making functions and variables (4,5 line) works in constant time (because it is, just different constant, but O(C)=O(1) for any constant C). When we make an array out of $$$n$$$ elements it takes $$$O(n)$$$ (7 line). It is the same as you make $$$n$$$ variables and we know that each can be made in $$$O(C)$$$, so we make $$$O(C\cdot n)=O(n)$$$ operations. The loop in the 8-10 lines takes also $$$n$$$ operations, since it uses all variables in the array. The loop in lines 11-13 works in $$$O(k)$$$, since it outputs only last k variables. Let's now rewrite all lines, but we will put how many operation does line take and not the code.


1.      O(1)
2.      O(1)
3.  
4.      O(1)
5.      O(1)
6.      O(1)
7.      O(n)
8-10.   O(n)
11-13.  O(k)
14.     
15.

Now, the overall complexity is just sum of complexities over all lines. In our case it is $$$O(1)\cdot 5+O(n)\cdot 2+O(k)$$$. As we remember, $$$O(n)+O(1)=O(n)$$$, so $$$O(n)+O(1)\cdot 5=O(n)$$$ and $$$O(n)+O(n)=O(n)$$$, so now complexity is $$$O(n)+O(k)=O(max(n,k))$$$ and since $$$n\ge k$$$, complexity is $$$O(n)$$$.

Example 2

Let's look at some harder case.

1.  #include <bits/stdc++.h>
2.  using namespace std;
3.
4.  int main(){
5.      int n,m;
6.      cin>>n>>m;
7.      for(int i=0;i<x;i++){
8.          for(int j=0;j<y;j++){
9.              cout<<i+j<<endl;
10.         }
11.     }
12.     return 0;
13. }

Let's analize all lines like we have done in the first example.

The new lines here are loop from 7 to 11 line and one more inside of it. Let's firstly analize loop in lines 8-10. It works in $$$O(y)$$$, since it takes $$$O(1)$$$ operation in line 9 for all j in range $$$[0,y)$$$ and there are y elements in that range. So, loop in lines 8-10 works in $$$O(y)$$$. When we look at loop in lines 7-11, we can see that i takes all values in range $$$[0,x)$$$, which is already $$$O(x)$$$ operations, but for each $$$i$$$ we make $$$O(y)$$$ operations in loop in 8-10 lines. So, it is working in $$$O(x)\cdot O(y)=O(x\cdot y)$$$. So, overall complexity is $$$O(x\cdot y)$$$.

Example 3

1.  #include <bits/stdc++.h>
2.  using namespace std;
3.
4.  int main(){
5.      int n;
6.      cin>>n;
7.      int a[n+1]={0};
8.      for(int i=1;i<=n;i++){
9.          for(int j=i;j<=n;j+=i){
10.             a[j]++;
11.         }
12.     }
13.     for(int i=1;i<n;i++){
14.         cout<<a[i]<<" ";
15.     }
16.     return 0;
17. }

This code finds number of divisors of number $$$i$$$ and memorize it in $$$a[i]$$$. Someone can see that it is just sieve of eratosthenes and because of this will say that this code works in $$$O(n\cdot log(n))$$$. It is really the right complexity, but we will try to analize this to get why it is.

We already saw all lines except 8-12 so we know that all of them works in $$$O(n)$$$. Let's look at the loop in 9-11 lines. It make $$$O(1)$$$ operation for each j which has divisor i and less then $$$n$$$. Number of such $$$j$$$ is $$$O(\frac{n}{i})$$$. Now when we look at loop in line 8-12, for some i it works in $$$O(\frac{n}{i})$$$ and it takes all $$$i$$$ in range $$$[1,n]$$$. So, the complexity is $$$O(\frac{n}{1})+O(\frac{n}{2})+O(\frac{n}{3})+O(\frac{n}{4})+O(\frac{n}{5})+...=O(n)+O(n)+O(n)+...=O(n)$$$ (because $$$O(n)+O(n)=O(n)$$$). It is typical mistake which is very easy to catch even for some who have very big expirience in programming. The fact is that, here we now a constant number of additives, so we cannot use rule $$$O(n)+O(n)=O(n)$$$. Here we can try to compute in another way. For easier intuition, we will remove $$$O()$$$ and now we need to compute $$$\frac{n}{1}+\frac{n}{2}+\dots+\frac{n}{n}=\sum_{i=1}^{n}\frac{n}{i}=n\cdot \sum_{i=1}^n\frac{1}{i}$$$. There exist one formula which is called harmonic series which is known to be at most then log of n. So, $$$\sum_{i=1}^n\frac{1}{i}\le log(n)$$$, so complexity is $$$O(n\cdot log(n))$$$.

As we see, computing complexity is same as just solving some math inequality. This is why we need to memorize some cases like harmonic series, to not have wrong thoughts about the complexity.

More advanced examples

There is popular algorithm named divide and conquerer. Using this algorithm, it is hard to analyze the code complexity. For example,

Code 1

#include <bits/stdc++.h>
using namespace std;

int a[100];

int find(int l,int r,int k){
    if(l+1==r){
        return a[l];
    }
    int m=(l+r)/2;
    if(a[m]>k){
        return find(l,m,k);
    }
    else{
        return find(m,r,k);
    }
}

int main(){
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    cout<<find(0,n,k);
    return 0;
}

One can note that it is just binary search algorithm. But in case we would not have if condition but go recursevily into both find fuunction, it seams that algorithm will work with really big complexity, but in fact it will work in $$$O(n)$$$. To analyze this code, we need additional notation. It is, $$$T(n)$$$. Really similar to $$$O(n)$$$ and in fact it is the same. It is needed to not have confusion when solving recursive time complexities. For example, we can denote first find function calling (from main) that it is $$$T(n)$$$, since we are looking for a value on $$$n$$$ other values. Then, we make number of values half of the number it was and just one additional operation to know which value to go. So, $$$T(n)=T(\frac{n}{2})+c$$$. Here, c is some constant. We will use it but not $$$O(1)$$$ and we will see why in a second. We can try to solve this just by iterating recursion. What I mean is that if $$$T(n)=T(\frac{n}{2})+c$$$, then $$$T(\frac{n}{2})=T(\frac{n}{4})+c$$$ so $$$T(n)=T(\frac{n}{4})+2\cdot c$$$. Using this, we can see that we can performe such operation $$$log(n)$$$ times, so $$$T(n)=T(\frac{n}{2^{log(n)}})+log(n)\cdot c$$$ and since $$$T(1)=1$$$, $$$T(n)=log(n)\cdot c=O(log(n))$$$. Here is why we used constant but not $$$O(1)$$$. It is because when we apply recursion, we get $$$2\cdot c$$$, which is also $$$O(1)$$$. In other words, it would be the same mistake as it was in the third example of previous section. Now, let's look at this code:

Code 2

#include <bits/stdc++.h>
using namespace std;

int a[100];

int find(int l,int r){
    if(l+1==r){
        return a[l];
    }
    int m=(l+r)/2;
    return find(l,m)+find(m,r);
}

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    cout<<find(0,n);
    return 0;
}

One can see that it just finds sum of whole array, so it is working linearly, i.e. $$$O(n)$$$, but we will get to it. So, here $$$T(n)=2\cdot T(\frac{n}{2})+c$$$ since we also make constant number of operations but go in recurssions two times but not 1 as in previous example. Also note, that $$$T(1)=1$$$ since if there is only 1 element we return it. So, if we apply recusion $$$T(n)=2\cdot T(\frac{n}{2})+c=4\cdot T(\frac{n}{4})+2\cdot c=2^x\cdot T(\frac{n}{2^x})+x\cdot c$$$. We end our recurssion when $$$n=1$$$, i.e. $$$x=log(n)$$$, so $$$T(n)=n+log(n)\cdot c=O(n)$$$. So, it works in linear time. We can also say that each element was checked one time and since number of elements is linear, code also works linear. This intuition is good enough, but sometimes it can be bad.

Here are some tasks for you if you want to practice with it:

Spoiler

Also, there exists Master theorem, which basicly solve some instances of the problem. There are not all of them, but in practice that is enough. Also, there is geeralization of it which is almost useless in practice, hard to understand but cool in some sence. So, here is master theorem. It is solving all recurences which looks like this: $$$T(n)=a\cdot T(\frac{n}{b})+c\cdot n^d$$$ for any a, b, d.