I am not able to calculate the Big O complexity of the partition function given in the code below. I tried to calculate it by estimating the number of nodes in the tree.

So far, I've figured out that from the start node, there will be n children, each that can have n/2 children at most (since the 2nd layer will pick from min(n, max) which will be n/2 at most), and so the 2nd layer will have n/4 children at every node at most, giving the tree a height of at most log(n).

We can better this, the first level will have n nodes. The second level will have at most 0+1+2+..+lim+lim-1+...1 nodes, and so on (where lim is ceil(n/2)). That gives n^2 nodes at each level, a total of log(n) levels, with O(n) work being done at each node. So, the complexity I get is O(n^3 log(n)).

But, I am not sure of my calculations, especially because clearly getting an upper bound for the partition function is not an easy problem (this paper: http://link.springer.com/article/10.1007%2Fs11139-007-9022-z#page-1 lists it as < c^(root(n)) ). Since that is exponential, my analysis must be wrong, but I'm missing where.

Can someone help?

The code is at: http://community.topcoder.com/stat?c=problem_solution&rm=310853&rd=14552&pm=11308&cr=22673583