0

What will be time complexity of the following function?

How can be the time complexity of inner loop be log(n)? it is given that the inner loop executes n/i times for each value of i.its running time is n*∑(from i=1 to n){n/i}.. and that i dnt get it

fucntion(n)
{ 
  for(int i=1;i<=n;i++)
  {
    for(int j=1;j<=n;j+=i)
    {
      printf("*");
    } 
  }
}
Walter Immanual
  • 1
  • 1

1 Answers1

1

In the first run of inner loop, we will loop n times. The second time we will skip every other number, so we loop n/2 times, then n/3 times, etc. This continues until the final loop where we go n/n = 1 pass through the loop.

As discussed here, 1 + 1/2 + 1/3 + ... + 1/n is O(log n). Since we are doing n times that, the resulting complexity is O(n log n).

Community
  • 1
  • 1
hcs
  • 1,514
  • 9
  • 14