22
Time Complexity Experiment..!!
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.
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.
void bigOn():
N <-- 0
time <-- 0
start:
N++;
if(time>1) break;
update(time);
print N#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);
}Value of n with O(n) complexity in 1 second:: 1540555
Note the value of n and lets discuss for 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.
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 nSo 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.
#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);
}Value of n with O(n^2) complexity in 1 second:: 1774
Note the value of n and lets discuss for 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.
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 nSo 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).
#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);
}Value of n with O(n^3) complexity in 1 second:: 168
Note the value of n and lets discuss for O(N^3).
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)
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 nSee 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.
#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);
}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:: 21It 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.
22