0 votes 0 votes What is the time complexity? int i,j,k,x=0; for(i=1;i<=n;i++) for(j=1;j<=i*i;j++) { if (j mod i ==0) for(k=1;k<=j;k++) x=x+10; } Algorithms time-complexity ace-test-series + – Sambhrant Maurya asked Aug 3, 2018 retagged Jul 9, 2022 by Lakshman Bhaiya Sambhrant Maurya 776 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments srestha commented Aug 3, 2018 reply Follow Share @Soumya what about if (j mod i ==0) how it effect on TC? 0 votes 0 votes Soumya29 commented Aug 3, 2018 reply Follow Share @Srestha, inner most for loop will run only when the value of j is some multiple of $i.$ 0 votes 0 votes shreyansh jain commented Jan 4, 2019 reply Follow Share @srestha In the innermost loop, termination condition is k<=j and j may go upto $n^2$ in worst case making it's complexity $O(n^2)$ but the runtime is limited by the condition you have mentioned, i.e. if (j mod i ==0) As j may go to $i*i$, following the above condition innermost loop will execute only if i divides j which will be equal to $j/i$ times i-count, j-count, no. of times (j%i==0) i = 1, j=1²,1 i = 2, j=2²,2 i = 3, j=3²,3 i = 4, j=4²,4 . . . . i = n, j=n²,n Hence innermost loop runs only $n$ times. So total complexity = $\sum i^2.O(n) = O(n^4)$ 0 votes 0 votes Please log in or register to add a comment.
Best answer 8 votes 8 votes $O(n^4)$ Soumya29 answered Aug 3, 2018 selected Aug 3, 2018 by srestha Soumya29 comment Share Follow See all 3 Comments See all 3 3 Comments reply srestha commented Aug 3, 2018 reply Follow Share @Soumya u r doing 2 summation, but actually there is only 1 summation right? 0 votes 0 votes Soumya29 commented Aug 3, 2018 reply Follow Share @Srestha. 2 summations are there. General term is - $i(1+2+3+.....+i)$ And value of i varies from 1 to n. 0 votes 0 votes Sambhrant Maurya commented Aug 3, 2018 reply Follow Share Thanks Soumya. Sometimes it's difficult to see how the summation series will be formed. 1 votes 1 votes Please log in or register to add a comment.