19

# 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 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.

```
#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 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).

```
#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 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.

```
#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:: 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.

19