Time Complexity Experiment..!!

Divay Mohan — Tue, 01 Jun 2021 09:19:02 +0000

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

Thank you so much for reading.

DEV Community: Divay Mohan

Time Complexity Experiment..!!

O(N):-

Algorithm:-

Code:

Output:-

O(N^2):-

Algorithm:-

Code:-

Output:-

O(N^3):-

Algorithm:-

code:-

Output:-

O(2^n):-

Algorithm:-

code:-

Output:-