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

[pastacode lang=”c” manual=”void%20fun()%0A%7B%0A%20%20%20int%20i%2C%20j%3B%0A%20%20%20for%20(i%3D1%3B%20i%3C%3Dn%3B%20i%2B%2B)%0A%20%20%20%20%20%20for%20(j%3D1%3B%20j%3C%3Dlog(i)%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%20printf(%22GeeksforGeeks%22)%3B%0A%7D” message=”” highlight=”” provider=”manual”/]Time Complexity of the above function can be written as Θ(log 1) + Θ(log 2) + Θ(log 3) + . . . . + Θ(log n) which is Θ (log n!)

Order of growth of ‘log n!’ and ‘n log n’ is same for large values of n, i.e., Θ (log n!) = Θ(n log n). So time complexity of fun() is Θ(n log n).

The expression **Θ(log n!) = Θ(n log n)** can be easily derived from following Stirling’s approximation (or Stirling’s formula).