efficiency of the closest pair algorithm

In T(n) = 2T(n/2) + M(n), where does the 2 in front of T come from. n/2 because it is dividing, and M(n) is linear, but I ca开发者_如何学Pythonn't figure out what the 2 is for?

2, because you are performing the operation on the two subsets. See the master theorem.

The recurrence relation is similar to what you get in Merge Sort. The time complexity would be O(n log n)

This says that the time cost of the problem of size n comes from dividing the problem in half (i.e., T(n/2)) and solving it for both halves (2 T(n/2)) plus some fix-up cost (i.e., M(n)).

So, the 2 is because you divide the problem in half and solve both halves.

The 2 represents how many times you're going to call the recurring function.

For example, if you had a tree that had 4 children, you would expect a 4 for that value. In this case, you're recurring twice.