1 Give an analysis of the running time BigOh notation for ea

1. Give an analysis of the running time (Big-Oh notation) for each of the following 4 program
fragments. You must provide calculate the computational cost of each line of code that shows how
you estimated the code snippet’s running time. Note that the running time corresponds here to the
number of times the operation sum++ is executed. sqrt is the function that returns the square root
of a given number.
(a)

sum = 0;
for(i=0;i<sqrt(n)/2;i++)
sum++;
for(j=0 ;j<sqrt(n)/4;j++)
sum++;
for(k=0;k<8+j;k++)
sum++;

(b)

sum = 0;
for(i=0;i<sqrt(n)/2;i++)
for(j=i;8+i;j++)
for(k=j;k<8+j;k++)
sum++;

(c)

sum = 0;
for(i=1;i<2*n;i++)
for(j=1;j<i*i;j++)
for(k=1;k<j;k++)
if (j % i == 1)
sum++;

(d)

sum = 0;
for(i=1;i<2*n;i++)
for(j=1;j<i*i;j++)
for(k=1;k<j;k++)
if (j % i)
sum++;

2. If it takes 10ms to run program (b) for n=100, how long will it take to run for n=400 ?

Solution

1.) For first questions, we have three independent loops. Out of which, first loop runs O(sqrt(n)) times. Similarly, second loop runs O(sqrt(n)) times. But third loop, executes as:

1+ 2+ ...+ sqrt(n) = sqrt(n)* (sqrt(n) +1) /2 = O(n).

So, overall complexity is O(n).

2.) Similary, in this case first loop will run O(sqrt(n)) times while secind loop runs O(n) times (as mentioned above) while most inner loop will be executed as:

1+2+..+n = n(n+1)/2 = O(n²).

So, overall complexity is O(n²).

3.) and 4.) Time complexity of both codes will be same.

Outer loop will run O(n) time.

Intermediate loop will run about

1 + 4+ 9 +... n² = {n*(n+1)*(2n+1)}/6 = n³ (approx.).

Now, inner loop will run like this:

1 + 8 + 27 + ... + n³ = {n*(n+1)}²/4 = n⁴ (approx.)

Therefore, overall code will run in O(n^4).

Hope it helps.