Download The Subset sum problem

T6,1 = 967,680
T7,1 = 42,577,920 (not shown in the table)
I checked the values that I got from the number of cases considered, for both Countdown12 and
Countdown13, when allowing the recursion to fully unwind to see if they were the same as these
values. Checking the results obtained by my program, see Appendix C, they are exactly the same as
the values calculated here. This is encouraging as it means that the values obtained from my program
are consistent with the theoretical analysis of the algorithm. It should be noted that the value of
cases considered for 4 numbers is given by “cases considered for 4 numbers”, as opposed to
“Number of cases considered”. This is because the complexity analysis calculated for each number,
is how many cases have to be considered just using that number of numbers, e.g. 6. However, the
“Number of cases considered” is the total number of cases considered using 2 numbers, 3 numbers,
…, 6 numbers.
Tn and Tn,1 will be upper bounds on the number of cases considered for Countdown12 and
Countdown13 because in practice the recursion is stopped early, either because of an illegal
operation, or because the target is found without using all the numbers.
It is clear from the results above that the bounds for Countdown13 is significantly less than that for
Countdown12. Moreover, the ratio of the bounds increases with n, as shown below.
n
2
3
4
5
6
7
Tn/Tn,1
1
1
1.2
1.7
2.9
5.5
32