retagged by
2,491 views
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++;

                 }

}
retagged by

1 Answer

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

Related questions

0 votes
0 votes
0 answers
2
0 votes
0 votes
1 answer
3
NeelParekh asked Jul 27, 2023
263 views
If an array is split in the form of increasing and decreasing order then what is TC to find minimum element in the array?
2 votes
2 votes
1 answer
4
h4kr asked Dec 30, 2022
432 views
What is the correct time complexity in $\theta()$ ?