Big O complexity of the partition function derived from this code?

Question

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)) ).

Can someone help?

int N = 0; 
ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>(); 
int[] scores; 

void partition(int n, int max, ArrayList<Integer> prefix) { 
    if (n == 0) { 
    results.add(prefix); 
    return; 
    } 

    for (int i = Math.min(max, n); i >= 1; i--) { 
        ArrayList<Integer> list = new ArrayList<Integer>(prefix); 
        list.add(i); 
        partition(n - i, i, list); 
    }
}

public int solve(int[] scores) { 
    N = scores.length + 1; 
    this.scores = scores; 
    partition(N - 2, N - 2, new ArrayList<Integer>());
    return 0;
}

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

Answer 1

Excellent asymptotics on the partition function are known, keep searching. Roughly, the number of partitions of $n$ is $\exp\Theta(\sqrt n) $ (much more is known). For each partition you are doing a polynomial amount of work, so the number of partitions dominates your runtime, which is also of the form $\exp\Theta(\sqrt n) $.