Question

For each of the following six program fragments give an analysis of the running time (Big-Oh will do). (25,very 5 mark)

(a)sum = 0;
for( i=0; i<n; i++ )
for( j=0; j<n; j++ )
sum++;
(b)
sum = 0;
for( i=0; i<n; i++ )
for( j=0; j<n*n; j++ )
sum++;

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

Answer 1

(a)

sum = 0;
for( i=0; i<n; i++ )
for( j=0; j<n; j++ )
sum++;

Let's first understand the above code line by line.

1. sum = 0. This is simply an initialization. It will take constant time. i.e O(1).

2. for( i=0; i<n; i++ )

  for( j=0; j<n; j++ )

So, There are two loops. One is Outer loop which run on i from 0 to (n-1). i.e n times, And other is inner loop which run from j from 0 to n-1 i.e n time

Value of i	Number of times, inner loop will run for value of i
0	n
1	n
2	n
...	...
...	...
n-1	n

So, here we are seeing that inner loop is running following number of times:

n + n + ... n times =

Here, terms with highest degree is

So, complexity of given code will be

(b)

sum = 0;
for( i=0; i<n; i++ )
for( j=0; j<n*n; j++ )
sum++;

Let's first understand the above code line by line.

1. sum = 0. This is simply an initialization. It will take constant time. i.e O(1).

2. for( i=0; i<n; i++ )

  for( j=0; j<n*n; j++ )

So, There are two loops. One is Outer loop which run on i from 0 to (n-1) i.e n times, And other is inner loop which run from j from 0 to n*n-1 i.e n*n times,

Value of i	Number of times, inner loop will run for value of i
0	n*n
1	n*n
2	n*n
...	...
...	...
n-1	n*n

So, here we are seeing that inner loop is running following number of times:

(n*n) + (n*n) + ... n times =

Here, terms with highest degree is

So, complexity of given code will be

(c)

sum = 0;
for( i=0; i<n; i++ )
for( j=0; j<i; j++ )
sum++;

Let's first understand the above code line by line.

1. sum = 0. This is simply an initialization. It will take constant time. i.e O(1).

2. for( i=0; i<n; i++ )

  for( j=0; j<i; j++ )

So, There are two loops. One is Outer loop which run on i from 0 to (n-1) i.e n times, And other is inner loop which run from j from 0 to i-1 i.e i times,

Value of i	Number of times, inner loop will run for value of i
0	0
1	1
2	2
...	...
...	...
n-1	n-1

So, here we are seeing that inner loop is running following number of times:

0 + 1 + 2 + ... + n-1 =

Here, terms with highest degree is

So, complexity of given code will be

(d)

sum = 0;
for( i=0; i<n; i++ )
for( j=0; j<i*i; j++ )
sum++;

Let's first understand the above code line by line.

1. sum = 0. This is simply an initialization. It will take constant time. i.e O(1).

2. for( i=0; i<n; i++ )

  for( j=0; j<i*i; j++ )

So, There are two loops. One is Outer loop which run on i from 0 to (n-1) i.e n times, And other is inner loop which run from j from 0 to i*i-1 i.e i*i times,

Value of i	Number of times, inner loop will run for value of i
0	0
1	1*1= 1
2	2*2=4
...	...
...	...
n-1	(n-1)*(n-1)

So, here we are seeing that inner loop is running following number of times:

Above came from formulae of sum of square of first n-1 natutal numbers.

Here, when we will multiply and expand above,  terms with highest degree will be

So, complexity of given code will be