CODEWITHSUNDEEP
algorithmasymptotic-complexity
Aaron
Aaron

Reputation: 105

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 can't figure out what the 2 is for?

Upvotes: 2

Views: 271

Answers (4)

corsiKa
corsiKa

Reputation: 82589

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.

Upvotes: 1

Emil Sit
Emil Sit

Reputation: 23552

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.

Upvotes: 1

YXD
YXD

Reputation: 32521

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

Upvotes: 4

Prasoon Saurav
Prasoon Saurav

Reputation: 92874

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

Upvotes: 1

Related Questions