ln n!

February 23, 2016

In the course of analyzing an algorithm, I used the simplifying hypothesis that the cost function is

\displaystyle c(n)\approx\sum_{i_1}^n \lg i=\lg n!.

That expression is cumbersome but we can get a really good simplified function to use as a proxy. Let’s see how.

Read the rest of this entry »

Stirling’s series

December 2, 2014

Last week, we had a look at how g++ handles tail-recursion. Turns out it does a great job. One of the example used for testing the compiler was the factorial function, n!.


We haven’t pointed it out, but the factorial function in last week’s example computed the factorial modulo the machine-size (unsigned) integer. But what if we want to have the best possible estimation?

Read the rest of this entry »