While solving some problems of time complexity, got stuck in the following code fragment

Question

What will be the time complexity of the following code?

    for(i=0;i<=n;i++)
     for(j=0;j<=log i;j++)
      print("hello world");

https://www.daniweb.com/programming/computer-science/threads/13488/time-complexity-of-algorithm here is an old (but still good) reference on how to calculate time complexity that might answer your question — Sterling Archer, Sep 13 '18 at 20:12
@user9335240 I disagree - it's on-topic here because it's a question about an algorithm. A bigger problem is that the OP doesn't show their prior attempt or research. — EJoshuaS - Stand with Ukraine, Sep 13 '18 at 20:14
[How to find time complexity of an algorithm](https://stackoverflow.com/q/11032015) — Bernhard Barker, Sep 13 '18 at 21:30

Kaidul · Answer 1 · 2018-09-13T20:30:45.450

2

Summing up the number of times the inner loop is iterating, we get,

log1 + log2 + log3 + log4 + ... + logN 
= log(N!)

And according to Stirling's approximation, log(N!) = O(N x log(N)) So the time complexity is O(NlogN)

edited Sep 13 '18 at 20:30

answered Sep 13 '18 at 20:14

Kaidul

1 Answers1