Calculate the factorial from the bottom up

According to my previous post about chain multiplication of 3 numbers, it's certain the most naive top to bottom recursive factorial algorithm that times itself by n*(n-1)*(n-2)...*2 is slower than the bottom to top 2*3*4....*n.
This post is about the proof of the concept.

T(n) as the time complexity of top to bottom multiplication for n!
B(n) as the time complexity of bottom to top multiplication for n!
The relationship can be presented like this
time complexity for two naive algorithms for factorial of n

How do we compare these two values? calculate those 2 functions from 1 to 10000 does show B(n) is faster and grow slower. It is good evidence, still it's not a proof. Let's work on the proof now.
Take off those floor function and the + 1, these have to little significance on the growth. Change log to general log instead of base 2 log. Easier on writing and the properties of each express will hold. Because all log functions have the same logarithmic growth rate. And in this general log, it's not possible to have a number lesser than one since there is a + 1 in the expression we can't see.

Suddenly, the entire expression became easier. It doesn't take a genius to see that:
in the B(n),
log k logarithmically increases
log((k-1)!) = increases at lesser than linearlogarithmic rate but faster than linear rate.
e^n < n! < n^n
n < log(n!) < log(n^n)
n < log(n!) < n log n

In T(n), log(n!/(n-k)!) is increasing and log(n-k) is decreasing
log(n!/(n-k)!) increases like log((k-1)!)
log(n-k) decreases logarithmically

T(n) might actually smaller than B(n)!
Let's put everything inside one log.

Now, we can take off this log sign. Why? because log is a continuous increasing function. so the relationship between both summations is still the same without the log. This same technique can be applied to the log in the exponents. Notice I have removed the B(n) and T(n). B(n) and T(n) are not approximate to the 2 expression right now, but each expression still corresponds to the same greater or lesser relationship between B(n) and T(n).

Now, because I don't have the most amazing brain in the world, I will do some cheat...
I removed the bases, only leave the exponents!
The growth of the exponents is WAY faster than the base(factorial growth VS linear growth), it's ok to ignore the base.
Note I have also changed the first expression's k's initial value to 1.
So everything come down to this comparison

n! is equal to n*(n-1)!, because the 2nd expression got a n!, it is greater than the 1st expression. so calculate factorial by multiply from 2 to n is faster than n to 2.
More rigor proof is required if I want to publish a paper...


Post new comment

The content of this field is kept private and will not be shown publicly.
If you have a Gravatar account, used to display your avatar.
  • Allowed HTML tags: <img> <a> <em> <strong> <cite> <code> <ul> <ol> <li> <dl> <dt> <dd> <span> <fn>
  • Lines and paragraphs break automatically.
  • Textual smileys will be replaced with graphical ones.
  • You can enable syntax highlighting of source code with the following tags: <code>, <blockcode>. Beside the tag style "<foo>" it is also possible to use "[foo]".
  • Use [fn]...[/fn] (or <fn>...</fn>) to insert automatically numbered footnotes.

More information about formatting options

What is 5 + 15?
To combat spam, please solve the math question above.
Honey Pot that kill bots