Time Complexity Experiment..!!
Tags: cpp, algorithms, timecomplexity, c
Published: 2021-06-01 09:19:02

This experiment is totally all about to understand the time complexity. Here, We are going to do reverse engineering means we will see in `1 second` how many similar operation could be performed in `O(n)`, `O(n^2)`,`O(n^3)` and `O(2^n)`. 

So lets start with `O(n)` time.
## O(N):- 
First question is that how to implement `O(N)` algorithm?
It is actually very easy to perform just iterate one loop for one second and count the number of iteration performed.
### Algorithm:-  
```
void bigOn():
  N <-- 0 
  time <-- 0
  start:
     N++;
     if(time>1) break;
     update(time);
  print N
```
### Code:
```
#include <stdio.h>
#include <time.h>
#include <math.h>
void big_o_n();
int main()
{
    //function to calculate the value of n using O(n) time
    big_o_n();
    return 0;
}
void big_o_n()
{
    clock_t start, end;
    unsigned int n = 0;
    double sec = 0;
    start = clock();
    while (sec < 1)
    {
        n++;
        end = clock();
        sec = (double)(end - start) / CLOCKS_PER_SEC;
    }
    printf("Value of n with O(n) complexity in 1 second::  %u\n", n);
}
```
### Output:- 
`Value of n with O(n) complexity in 1 second::  1540555`
Note the value of `n` and lets discuss for `O(N^2)`.
## O(N^2):-
This time it is little bit tricky to implement an algorithm with `O(N^2)` time complexity when we actually don't know the value of `N`, Instead we have to calculate the value of `N`.

Are you excited to do that? lets do that.
As we know from our 10 standard's mathematics book sum of first `N` Natural numbers is  `N(N+1)/2`. So we can use this property to perform this experiment.
`1+2+3....+N = N(N+1)/2    <-----Eq(1)`
So what we can do just start a loop for one second and inside this loop we can iterate another loop for `i` times where `i` incremented by `1` for every outer loop iteration. So for more clarity let see the algorithm.
### Algorithm:- 
```
void bigOnSquare():
     time <-- 0
     n <-- 0
     i <-- 1
     sts <--false
     while(i):
         n <-- n+1
         for j <-- 0 to i:
              update(time)
              if time>=1:
                  sts <-- true
                  break     
         if sts:
            break
         i<-- i+1
     print n   
```
So in above algorithm we have initialized `i` with `1` and inner loop every time iterate `i` times. we are incrementing value of `i` by `1` in every outer loop iteration. This means that inner loop will be iterate `1 + 2 + 3. ..... times` for one second 
and we know that from `equation 1`: `1+2+3..+n = n(n+1)/2` which is nothing but the operation performed for `O(n^2)` times.

### Code:-  
```
#include <stdio.h>
#include <time.h>
#include <math.h>
void big_o_n_square();
int main()
{
    //function to calculate the value of n using O(n^2) time
    big_o_n_square();
    return 0;
}
void big_o_n_square()
{
    clock_t start, end;
    unsigned int n = 0;
    double sec = 0;
    int sts = 0;
    start = clock();
   
    for (int i = 0;; i++)
    {
          n++;
          for (int j = 0; j < i; j++)
          {
             end = clock();
             sec = (double)(end - start) / CLOCKS_PER_SEC;
             if (sec >= 1)
             {
                 sts = 1;
                 break;
              }
          }
          if (sts == 1)
          {
             break;
          }
    }
    
    printf("Value of n with O(n^2) complexity in 1 second::  %u\n", n);
}
```
### Output:- 
`Value of n with O(n^2) complexity in 1 second::  1774 `
Note the value of `n` and lets discuss for `O(N^3)`.

## O(N^3):- 
Similar to `O(N^2)` experiment it is also based on a well defined formula. But what is it? Think and then go ahead.
So let's discuss the formula. We know this formula from `10th` standard which is nothing but the sum of squares of first `n` natural numbers.
`1^2+2^2+….+n^2= n(n+1)(2n+1)/6  <------------Eq(2)`
This experiment is same as O(N^2) but difference is that instead of one inner loop we will have 2 nested inner loops. Again we will initialize i with 1 and increment it by 1 for every iteration of outer loop. Inner nested loops iterate for i^2 times for every i th iteration of outer loop. For more clarity let see the algorithm.
### Algorithm:- 
```
void bigOnCube():
     time <-- 0
     n <-- 0
     i <-- 1
     sts <--false
     while(i):
         n <-- n+1
         for k <--0 to i:
             for j <-- 0 to i:
                  update(time)
                  if time>=1:
                      sts <-- true
                      break     
             if sts:
                break
         if sts:
             break 
         i<-- i+1
      print n   
```
So read algorithm carefully and you will find that it is following the formula given in Eq(2) which have time complexity of O(N^3).
### code:- 
```
#include <stdio.h>
#include <time.h>
#include <math.h>
void big_o_n_cube();
int main()
{
    //function to calculate the value of n using O(n^3) time
    big_o_n_cube();
    return 0;
}
void big_o_n_cube()
{
    clock_t start, end;
    unsigned int n = 0;
    double sec = 0;
    int sts = 0;
    start = clock();
    
    for (int i = 0;; i++)
    {
        n++;
        for (int j = 0; j < i; j++)
        {
            for (int k = 0; k < i; k++)
            {
                end = clock();
                sec = (double)(end - start) / CLOCKS_PER_SEC;
                if (sec >= 1)
                {
                    sts = 1;
                    break;
                }
            }
            if (sts == 1)
            {
                break;
            }
        }
        if (sts == 1)
        {
            break;
        }
    }
    
    printf("Value of n with O(n^3) complexity in 1 second::  %u\n", n);
}
```
### Output:- 
`Value of n with O(n^3) complexity in 1 second::  168`
Note the value of `n` and lets discuss for `O(N^3)`.
## O(2^n):-
This particular algorithm is also based on the mathematical equation. The sum of first `n` power of `2` is equal to `2^(n+1) -1`. which is nothing but the `O(2^n)` which is also called as `exponential` time complexity. If you want you can google this algorithm and find the explanation. But for now lets first see the equation and then implement it.
` 2^0 + 2^1 + 2^2 + 2^3 + …. + 2^n-1 = 2^n - 1 <<----------Eq(3)` 
### Algorithm:- 
```
void bigOnSquare():
     time <-- 0
     n <-- 0
     i <-- 1
     sts <--false
     while(i):
         n <-- n+1
         for j <-- 0 to pow(2,i):
              update(time)
              if time>=1:
                  sts <-- true
                  break     
         if sts:
            break
         i<-- i+1
     print n   
```
See in the above algorithm we have initialized i to 1 and increment it by 1 in outer loop. For every ith iteration of outer loop inner loop will iterate for 2^i times. Which is direct implementation of Eq(2). Let's see its code and output.
### code:- 
```
#include <stdio.h>
#include <time.h>
#include <math.h>

void exponential();
int main()
{
    //function to calculate the value of n using O(2^n) time
    exponential();
    return 0;
}
void exponential()
{
    clock_t start, end;
    unsigned int n = 0;
    double sec = 0;
    int sts = 0;
    start = clock();
   
    for (int i = 0;; i++)
    {
        n++;
        for (int j = 0; j < pow(2, i); j++)
        {

           end = clock();
            sec = (double)(end - start) / CLOCKS_PER_SEC;
            if (sec >= 1)
            {
                sts = 1;
                break;
            }
        }
        if (sts == 1)
       {
            break;
       }
    }
    
    printf("Value of n with O(2^n) complexity in 1 second::  %u\n", n);
}
```
### Output:- 
`Value of n with O(2^n) complexity in 1 second::  21`
Note the value of n.

So finally we get:
```
Value of n with O(n) complexity in 1 second::  1540555
Value of n with O(n^2) complexity in 1 second::  1774
Value of n with O(n^3) complexity in 1 second::  168
Value of n with O(2^n) complexity in 1 second::  21
```
It is fun doing this experiment because we get a sense how time complexities are different from each other.

Hope you enjoyed it. Please suggest edits if any.
You can find this experiment code at: [Code](https://github.com/divaymohan/M.tech_Lab_work/tree/master/19MCMT28_ITLAB_1)

Thank you so much for reading.