The Gateway to Computer Science Excellence
+2 votes
199 views
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++;

                 }

}
in Algorithms by Active (1.2k points) | 199 views
0

O(n4)  ?

0
Yes...But How???

1 Answer

+1 vote

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 ...

by Loyal (8.2k points)
0
@hs yadav how k is 2 times 4 similarly  how 3 times 9 please explain
+1

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)

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,364 answers
198,492 comments
105,260 users