Complexity quiz issue

#1

please explain in detail the question 2 and question 5 of the quiz.i have seen the answers but can not understand

#2

Please paste the questions here.

#3

question 2 void function(int n) { int count = 0; for (int i=0; i<n; i++) for (int j=i; j< ii; j++) if (j%i == 0) { for (int k=0; k<j; k++) printf(""); } }

#5

sorry the id send is for question 5

#7

Check this for ques 5

#8

void function(int n)
{

int count = 0; 
// executes n times 
for (int i=0; i<n; i++) 

    // executes O(n*n) times. 
    for (int j=i; j< i*i; j++) 
        if (j%i == 0) 
        { 
            // executes j times = O(n*n) times 
            for (int k=0; k<j; k++) 
                printf("*"); 
        }

}
So time Complexity for ques 2 is O(n^5).

#9

please give the sigma equation for i in ques 2

#10

please give the sigma equation in i for ues 2

#11

It is not required. You can clearly see and get it. Time complexity can be analyzed by checking how many times the innermost statement is being executed.
The outermost loop runs for n or say n-1 times since maxm value of i is of order n.
Then the second loop yo ucan see that j is dependent on i and the maxm time it can run is i * i …Since you know maxm value of i is n…so i * i = n * n
Now the last loop is dependent on j…and the maxm time i can run is j which is equal to n * n (from previous steps)
So clearly the innermost statement will be executed n * (n * n) * (n * n) So complexity is O(n^5)

#12

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#13

but the point i am not understanding in the second question is that the k loop is not running for all values of j so how can u take that if j loop is executed n2 times then k loop will be executed n2 times?

#14

I hope @pratyush63 has cleared your doubt, but if you still want any help do let me know , I would be happy to help :grinning:

#15

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.