3 votes 3 votes What is the time complexity of the following code? void foo(int n) { int s=0; for( i=1 ; i<=n ; i++ ) for( j=1 ; j<= i*i ; j++) if( j%i==0 ) { for( k=1 ; k<=j ; k++ ) s++; } } Algorithms time-complexity algorithms + – Harsh Mehta asked Jan 16, 2018 • retagged Jul 9, 2022 by Lakshman Bhaiya Harsh Mehta 2.5k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply hs_yadav commented Jan 16, 2018 reply Follow Share O(n4) ? 0 votes 0 votes Harsh Mehta commented Jan 16, 2018 reply Follow Share Yes...But How??? 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes see when... i=1 j=1 k=1 i=2 j=1-4 k=2.times 4 i=3 j=1-9 k=3 times 9 ........ ........ i=n j=1-n2 k=n times n2 so overall running time .. 1+2.22+3.32+4.42+.....+n.n2 or $\sum i3$ where 1=<i =<n ... hs_yadav answered Jan 16, 2018 hs_yadav comment Share Follow See all 2 Comments See all 2 2 Comments reply eyeamgj commented Jan 30, 2018 reply Follow Share @hs yadav how k is 2 times 4 similarly how 3 times 9 please explain 0 votes 0 votes hs_yadav commented Jan 30, 2018 reply Follow Share k would be...like this.. i=2 (2+4)-> 2(1+2) i=3 (3+6+9)->3(1+2+3) i=4(4+8+12+16) ->4(1+2+3+4) or we can write it ..4(n(n+1))/2 or 4.O(n2) or 4.(42) 1 votes 1 votes Please log in or register to add a comment.