How can I evaluate an algorithm for a NP-Hard problem?
It doesn't matter for what the algorithm is for, that is, you can analyze an algorithm for an easy problem (e.g. sorting) just like you would analyze an algorithm for a hard problem (e.g. 3-SAT). So the question does make sense.

Think about how your brute force method works. If you try all partitions of nodes, how many possible partitions are there? This is the way your analysis should work. Given that the problem is NP-hard, one should not expect a polynomial time algorithm though, but that's fine.