retagged by
2,984 views
3 votes
3 votes

What is the time complexity of following function fun()? Assume that log(x) returns log value in base 2.

void fun()
{
   int i, j;
   for (i=1; i<=n; i++)
      for (j=1; j<=log(i); j++)
         printf("GeeksforGeeks");
}
retagged by

2 Answers

Best answer
2 votes
2 votes
j is dependent on i, therefore unroll the dependency, means analyze for i only

if i=1 ----> inner loop executes log(1) times

if i=2 ----> inner loop executes log(2) times

if i=3 ----> inner loop executes log(3) times

.

.

if i=n ----> inner loop executes log(n) times.

 

combine them ==> log(1)+log(2)+.....+log(n) = log ( 1.2.3...n ) = log ( n! ) = n log(n)
selected by

Related questions

0 votes
0 votes
1 answer
1
I_am_winner asked Sep 6, 2018
356 views
f(n)>=c1.nh(n)=c2.nthen why answer cant be O(n),It is given as C
2 votes
2 votes
1 answer
2
gauravkc asked Apr 5, 2018
860 views
What is the time complexity of this code?
2 votes
2 votes
1 answer
3
92komal asked Jan 26, 2018
369 views
plz help me . how to solve that type of question
1 votes
1 votes
1 answer
4