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.
Nope. It looks like it at first glance, but it isn't.
Look at what happens when n == b/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.