3. The city of San Juan commissions you to design a new bus system for Old San Juan which has n stops numbered 1, 2, . . . , n on the North-bound route (lets ignore the South-bound route). Commuters may begin their journey at any stop i and end at any other stop j > i.

Use a divide-and-conquer technique to design a bus system that uses (n log n) route segments and which requires a person to wait through at most 1 extra segment when going from any i to any j (as long as i j, i.e., we only consider North-bound routes for simplicity, and all buses run North). In other words, a commuter can travel from any i to any j by using at most 2 segments.

1 (a) For the base cases n = 1, 2, design a system using at most 1 route.

(b) For n > 2 we will use divide-and-conquer. Assume that we already put in place routes connecting the first n/2 stops and routes connecting the last n/2 stops so that if i and j both belong to the same half, we can get from i to j in at most 2 segments. Show how to add O(n) additional routes so that if i is in the first half and j is in the second half we can get from i to j in 2 segments.

(c) Write the recurrence for the number of routes your solution use and solve it using the master theorem