Forty Items Two Halves

You have 40 weights and a target sum, and you must decide whether some subset hits the target exactly. Enumerating all subsets is $2^{40} \approx 1.10 \cdot 10^{12}$ , far too slow.

You split the 40 into two halves of 20, enumerate all $2^{20} = 1,048,576$ subset sums of each half, sort the left list, and for every right-half sum binary search the left list for the complement.

Roughly how many elementary operations does that plan cost?

About $1.1 \cdot 10^{12}$ : splitting the input changes the constant factor but not the exponential term.

About $4 \cdot 10^7$ : $2 \cdot 2^{20}$ sums to generate, plus $2^{20} \cdot 20$ to sort one half, plus $2^{20} \cdot 20$ binary search steps.

About $2 \cdot 10^6$ , just the $2 \cdot 2^{20}$ subset sums, since sorting and searching are lower-order.

About $1.1 \cdot 10^{12}$ , because every left sum still has to be checked against every right sum, and $2^{20} \cdot 2^{20} = 2^{40}$ .