Gate2017 ss Q48

0. Consider the following C function

(int fun (int n) {
int i, j;
for (i = 1; i < = n; i++) {
for (j = 1; j < n ; j+=i) {
printf (“%d %d, i, j ) ;
}
}
})
Time complexity of fun in terms of θ notation is

Answer
Comment
Array

Option : C
Explanation :
for i = 1
j will run from 1 to n by incrementing by '1' in each step 'j 'will run for n times
For i=2
j will run from 1 to n by incrementing by ‘2’ in each step j will run for n/2 times

next time j will run for n/3 times
and so on

time complexity = n + n/2 + n/3 + n/4 + .....
= n(1+1/2+1/3+.....)
=nlogn

Forgot your password?

I agree with the Terms.