News for hackers. Stuff that matters.
Re:Using Monads in C++ to Solve Constraints: 1. The List Monad by TheLoneWolfling on Wednesday May 13, 2015 @04:06PM (#9541605)
> 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.

Re:Using Monads in C++ to Solve Constraints: 1. The List Monad by dllthomas on Wednesday May 13, 2015 @04:27PM (#9541726)
b!/(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.

Re:Using Monads in C++ to Solve Constraints: 1. The List Monad by TheLoneWolfling on Wednesday May 13, 2015 @04:52PM (#9541888)
Whoops, started with C = 2 and generalized, incorrectly it would seem. I'll edit it.

Edit: edited.

Re:Using Monads in C++ to Solve Constraints: 1. The List Monad by dllthomas on Wednesday May 13, 2015 @05:35PM (#9542130)
Thanks :) C = 2 was enough, of course. So O(n!) is between O(k^n) and O(n^n)?
Re:Using Monads in C++ to Solve Constraints: 1. The List Monad by TheLoneWolfling on Wednesday May 13, 2015 @08:12PM (#9542800)
Yep. Though we often weaken a big Theta of n! to a big O of n^n, as it's easier to deal with.
Re:Using Monads in C++ to Solve Constraints: 1. The List Monad by dllthomas on Wednesday May 13, 2015 @08:30PM (#9542841)
That makes sense, and probably contributed to my confusion.