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”/] [ad type=”banner”]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).
[ad type=”banner”] [pastacode lang=”c” manual=”%20%20%20log%20n!%20%3D%20n%20log%20n%20-%20n%20%2B%20O(log(n))%20″ message=”” highlight=”” provider=”manual”/]