5 ms·
> I believe that b!/(b-n)! is asymptotically the same class as b^n Nope. It looks like it at first glance, but it isn't. Look at what happens when n == b/C:
by TheLoneWolfling 11y ago
> I believe that b!/(b-n)! is asymptotically the same class as b^n
Nope. It looks like it at first glance, but it isn't.
Look at what happens when n == b/C:
b^(b/C) / (b!/(b - b/C)!) ==
b^(b/C) / (b!/(b*(C-1)/C)!) ==
e^(log(b^(b/C)) + log((b/C)!) - log((b*(C-1)/C)!)) ~=
e^(b/C log(b) + [b*(C-1)/C] log (b*(C-1)/C) - [b*(C-1)/C] - b log b + b) ==
e^((b+b (-1+C) log((-1+C)/C))/C) ==
e^(b/C* (1+(C-1)log((C-1)/C)))
(I used Stirling's Approximation, namely the form ln(x!) ~= x ln x - x for large x)
However, note that (1+(C-1)log((C-1)/C)) / C is greater than zero for all C > 1, as 1+(C-1)log((C-1)/C) > 0 for all C > 1. As such, this diverges for all C > 1.
- dllthomas 11y agob!/(b-n)! only = b!/(b/C)! when C = 2, but interesting regardless. I'll revisit when I have the chance. In any case, I make the assertion that the algorithm proposed in the article is in fact O(b!/(b-n)!), with the intended definition of StateL.
- TheLoneWolfling 11y agoWhoops, started with C = 2 and generalized, incorrectly it would seem. I'll edit it. Edit: edited.
- dllthomas 11y agoThanks :) C = 2 was enough, of course. So O(n!) is between O(k^n) and O(n^n)?
- TheLoneWolfling 11y agoYep. Though we often weaken a big Theta of n! to a big O of n^n, as it's easier to deal with.
- dllthomas 11y agoThat makes sense, and probably contributed to my confusion.