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

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”/]

## Worst Average and Best Cases

We will take an example of Linear Search and analyze it using Asymptotic analysis.We can have three cases to analyze an algorithm:Worst,Average,Best

## Space Complexity mean

Space Complexity mean – Analysis of Algorithm The term Space Complexity is misused for Auxiliary Space at many places. Following are the correct

## Time Complexity of Loop with Powers

Time Complexity of Loop with Powers- Analysis of Algorithm What is the time complexity of below function?Time complexity of above function can be written as

## NP Completeness

NP Completeness- Analysis of Algorithm – In this post,failure stories of computer science are discussed.Can all computational problems be solved by a computer

## Solving Recurrences

Solving Recurrences – Analysis of Algorithm -Many algorithms are recursive in nature. When we analyze them, we get a recurrence relation for time complexity

## Pseudo polynomial Algorithms

pseudo polynomial Algorithms – Analysis of Algorithm – An algorithm whose worst case time complexity depends on numeric value of input (not number of inputs)