Possible partitions, for k-means problem(k=2) I have this brute-force algorithm to solve the problem:

Generate all possible partitions of P into two subsets of P1 and P2

For each partition P1, P2 generated in Step 1, compute the cost of the partition

Report the partition with the lowest cost found in Step 2.


How can I analyze the number of possible partitions and use that to determine the running time?
If $(P_1, P_2)$ is a partition of $P$, that means that $P_2 = P\setminus P_1$.
That means that is suffices to count the number of possible choices of $P_1$, which is the cardinal of the powerset of $P$, $|\mathcal{P}(P)| = 2^{|P|}$.
If $P_1$ and $P_2$ have symmetrical roles, you can divide the result by $2$ (but it does not change the asymptotical complexity).