Explaining Runtime of Shamos Algorithm

[AkilMAI]

Can someone please explain to me why the recursive part of this algorithm has the runtime
T(n) = {O(1), if n ≤ 3;
{Tf(n/2) + Tc(n/2) + O(n), if n > 3.

->where Tf(n/2) represents the floor function of T(n/2) and Tc(n/2) represents the the ceilling function

It is called Shamos algorithm and the main steps are:
1. If n ≤ 3 find the closest points by brute force and stop.
2. Find a vertical line V such that divides the input set into two disjoint subsets PL and PR of size
as equal as possible . Points to the left or on the line
belong PL and points to the right or on the line belong to PR. No point belongs to both since
the sets are disjoint.
3. Recursively find the distance δL of a closest pair of points in PL and the distance δR of a closest
pair in PR.
4. Let δ = min(δL, δR). The distance of a pair of closest points in the input set P is either that of
the points found in the recursive step (i.e., δ) or consists of the distance between a point in PL
and a point in PR.
(a) The only candidate points one from PL and one from PR must be in a vertical strip consisting
of a line at distance δ to the left of the line V and a line at distance δ to the right of V
(b) Let YV be an array of the points within the strip sorted by non-decreasing y coordinate
(i.e., if i ≤ j then YV ≤ YV [j]).
(c) Starting with the first point in YV and stepping trough all except the last, check the distance
of this point with the next 7 points (or any that are left if there are not as many as 7). If a
pair is found with distance strictly less than δ then assign this distance to δ.
5. Return δ.
Thanks.

 

[Future Bruno]

The recursive part of this algorithm essentially reduces the problem size by half at each step. This is what allows it to have a runtime of T(n) = {O(1), if n ≤ 3; {Tf(n/2) + Tc(n/2) + O(n), if n > 3. At each step, the algorithm divides the problem in half and then recursively calls itself on the two halves (Tf(n/2) + Tc(n/2)). The O(n) part is because of Step 4b, where the algorithm must scan through the points in the vertical strip (YV). Since there are n total points, the runtime for scanning through them is O(n).