• $$$O$$$: $$$f(x)=O(g(x))\Longleftrightarrow \exists n_0\in \mathbb{N}, C\in \mathbb{R} s.t. \forall n \ge n_0,$$$ then $$$|f(n)|\le C\cdot g(n)$$$ or in words, after some point there exist a constant such that function f is smaller then function g times C

• $$$o$$$: $$$f(x)=O(g(x))\Longleftrightarrow \lim_{n\rightarrow \inf} \frac{f(n)}{g(n)}=0$$$ or in words, after some point, f(n) will eventually be much bigger then g(n).

• $$$\Omega$$$: $$$f(x)=\Omega (g(x))\Longleftrightarrow g(x)=O(f(x))$$$.

• $$$\omega$$$: $$$f(x)=\omega (g(x))\Longleftrightarrow g(x)=o(f(x))$$$.

• $$$\Theta$$$: $$$f(x)=\Theta (g(x))\Longleftrightarrow f(x)=O(g(x))$$$ and $$$f(x)=\Omega(g(x))$$$.

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)$$$.

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)$$$.

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))$$$.