A Time Complexity Question

A Time Complexity Question – Analysis of Algorithm What is the time complexity of following function fun()? Assume that log(x) returns log value in base 2.
Total
8
Shares
A Time Complexity

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).

[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”/]
Leave a Reply

Your email address will not be published. Required fields are marked *

You May Also Like