Test-series algorithms

Question

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");
}

Comments

$\sum_{i=1}^{n}\sum_{j=1}^{\log i}1=\sum_{i=1}^{n} \log i$

$=\log 1 +\log 2+ \log 3 +...\log n=\log (1\times 2\times 3 ..\times n)=\log (n!)=n \log n$

Answer 1

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)

Answer 2

I hope it will be help you

https://stackoverflow.com/questions/29556801/complexity-when-loop-runs-log-times