Question

Q)Determine the complexity of the following code chunks.

Show all calculations. (Assume that f() has complexity O(1)).

A)for(i=0; i<n; i++) m += i;

B) for(i=0; i<n; i++)

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

                            sum[i] += entry[i][j];

C) for(i=0; i<n; i++)

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

                            m += j;

D) i= 1;

while(i< n)

{ tot += i;

i= i* 2;}

E) i= n;

while(i> 0) {

tot += i;

i= i/ 2; }

F) for(i=0; i<n; i++)

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

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

                                       sum[i][j] += entry[i][j][k];

G) for(i=0; i<n; i++)

                    for(j=0; jn; j++)

                                 sum[i] += entry[i][j][0];

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

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

                        sum[i] += entry[i][0][k];

H) for(i=0; i<n; i++)

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

                                     m += j;

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

         for(j=0; j< sqrt(995); j++)

                      m += j;

J) int total(int n)

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

                  subtotal += i;

main()

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

tot += total(i);

K) for(i=0; i<n;i++) {

subtotal = 0;

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

                subtotal += j;

tot += subtotal;}

Answer 1

a) O(n)

The loop is executed n times and addition takes O(1) times.

===============

b) O(n^2)

There are two nested loops. For each value of i, j is executed n times. Also i loop is executed n times. The loop body takes constant time. So total of n^2 times loop body is executed. Hence time complexity = O(n^2)

===============

c) O(n^2)

Total no. of times loop body is executed = 0 + 1 + 2 + .. n-1 = n*(n-1)/2 = O(n^2)

================

d) O(logn)

The loop runs for i = 1,2,4,8,.. 2^k. So it runs for k times where 2^k <= n but 2^(k+1) >n.

So 2^k = n.

Hence k = logn.

Hence time complexity = O(logn)

==================

e) O(logn)

Loop runs for i = n,n/2, n/4,n/8... n/2^k

Loop terminates when n/2^k < 1

HEnce k = logn times loop runs.

===================

f) O(n^3)

Three nested loops each running n times.

=======================

g) O(n^2)

The first and second nested loop runs n^2 times both. So total of 2n^2 times. Which is O(n^2)

=======================

H) O(n^1.5)

The outer loop runs n times and for each value inner loop runs sqrt(n) times. Hence n*n^0.5 = n^1.5 times.

======================

I) O(n)

It runs for sqrt(995)*n = 31n times approx.Hence O(n)

=====================

J) O(n^2)

Total function runs for n times.

It is called from main for values 0,1,2.. n-1 times. So n*(n-1)/2 times subtotal+=i; statement is run. Hence O(n^2)

=======================

K) O(n^2)

Similar to above part J. But within nested loop only.

========================

Please upvote.