Time Complexity of Iterative Program

Question

The innermost loop will execute when j is multiple of i, and that will happen exactly i times. Please help me to find the time complexity of the below program:

Comments

uploading soon :D

---

but as solution not as comment

---

Hey what if we make a minor change to the code:

In the second for loop: initialize j = i instead of j=1.

The complexity should remain the same, right?

Answer 1

For a given i, How many times if ( j % i == 0)  is true?

(For a given i), j can take the value 1, 2, 3, ....... (i * i).

So, whenever j take the value i, 2i, 3i, ..... (i*i). The condition if ( j % i == 0) is true.

So, for a given i, the condition if ( j % i == 0) is true for exactly i times. (Important).

Whenever the condition (if) is true how many times the innermost loop will execute?

For a given i, j can take the value 1, 2, 3, ....... (i * i).  (As mentioned above).

when j = i, the if condition is true, And the innermost loop will run i times.

when j = 2i, the if condition is true, And the innermost loop will run 2i times.

And so on,

When j = i * i, the if condition is true,  And the innermost loop will run i*i times.

Therefore, for a given i, the innermost loop will run for ( i + 2i + 3i + 4i + ....... + i*i) times.

And i will vary from i = 1 to n.

$\Rightarrow$  T(n) = $\sum_{i = 1}^{n} (i + 2i + 3i +..... (i*i))$

T(n) = $\sum_{i = 1}^{n} i*(1 + 2 + 3 + ...... i))$

T(n) = O($n^{4}$)

Comments

you perfectly answered this question! thank you!!
can you help me to understand following solution given on a website for this same question:

I want to understand his logic, why is the innermost loop is executed upto i*j?

---

The condition if ( j % i == 0) is true i times for a given i. They are saying this, in the first line.

Now, they are running the second loop only i times. But the question you posted it is running i*i times.

Now j_prime can take the value i, 2i, 3i, so on i*i.

And we run the innermost loop for j_prime times.

So the innermost loop will run for i + 2i + 3i + 4i + ....... i*i.

 

At which site you are practicing these question? Is it interviewbit.com?

---

there is no specific website, i randomly found this question on internet.

Answer 2

time complexity will be O(n⁴)

Comments

https://goo.gl/9NqocL

 

#include <stdio.h>
#include <math.h>
int main()  //while using gcc compiler use gcc -o main*.c -lm
{

 int i,j,k;
 double sum=0.0,n=5,temp;//set n value here !!
 for(i=1;i<=n;i++)
    for(j=1;j<=(i*i);j++)
        if(j%i==0)
            for(k=0;k<j;k++)
                {printf("j=%d k=%d\n",j,k);
                sum++;
                }
                
printf("sum is %lf\n",sum);
temp=log(sum)/log(n);
printf("time complexity will be around %lf\n",temp);
    return 0;
}

Now, for more big values of n it is going towards O(n^4). 

---

when i=1. then j= 1 to 1. then how will k execute two times?

Answer 3

T(n)=2T(n/2)+n^2 rr equation of recusive program

So O(n)^2