MadeEasy Test Series: Algorithms - Time Complexity

Question

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

find time complexity of these program?

Answer 1

(The third loop executes only when j%i == 0, which will be true for j = i, 2i, 3i, ... i*i. i.e., it also executes i times. )

We have to count the number of times the statement $c = c + 1;$ is executed.

the outer $i$ loop executes from $1 .. n$.

for $i = 1, 2, 3, 4, \dots n$

the $k$ loop will execute for $j$ values

$(1), (2,4), (3,6,9), (4,8,12,16), \dots ,\left(n,2n,3n,\dots n^2\right)$

So, we have to count the iterations for k, which will give

$\sum_{i=1}^{n} \sum_{j=1}^{i} j \times i \\
= \sum_{i = 1}^{n}i.\sum_{j=1}^{i} j
\\= \sum_{i=1}^{n} i  \frac{i.(i+1)}{2}
\\= \sum_{i=1}^{n} \frac{i^3+i^2}{2}
\\= O(n^4)$

(We can assume the sum to the cubes of first n natural numbers)

Comments

Arranging the terms we can get

(1+2+3+4+...)+(4+6+8+....)+(9+12+...)

but can't find how to derive an expression for it?

:(

---

@arjun sir how i*j in summation have been derived..

---

see now..

Answer 2

I am not sure but see what we get.

i =  1  |   2  |   3  |   4  |  5   |  6  ........................n

j =  1t  | 4t  |  9t  | 16t | 25t |36t.................n^2t.                (t represent times)

k =  1   |   (2t 4t) |  (3t 6t 9t) | .................................

seeing just last value in every set we have

n(1 + 4 + 9 + 16 +...............n^2) + some constant

which is O(N4).

Answer 3

Time complexity of first loop will be n

Time complexity of second loop will be ((n^3/3)+(n^2/2)+(n/6))

Time complexity of third loop will be n*n^3

So, Total Complexity will be: O(n^4)

Answer 4

i varies from 1 to n

j varies from 1 to n*n

now j%i==0 follows 1 to n, 2n,3n,4n...n*n =2n-1 times

and k varies from 1 to n*n

therefore Time is proportional to n^6.

Is that right?

Comments

how 2n-1 ? adding in tc???

---

i divides j if j is a multiple of i. Since i takes values from 1 to n and j takes from 1 to n*n, i divides j when (i,j)= {(1,1).(2,2)....(n,n),(n,2n),(n,3n)....(n,n*n)). and cardinality of this set is n+n-1.Let me know if I am wrong.

---

But you talking about value but here the issue is tc.

While determining tc no of statement does not matter.

All statement takes constant time.

---

ok