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. There are some obvious options:

(a) You can have a bus run from the southern-most point to the northernmost point as a traditional busline might run. The system would be cheap because it only requires n segments for the entire system. However, a person traveling from stop i = 0 to stop j = n must travel through all n segments. This system will be slow for that person.

(b) You can have a special express bus run from every point to every other destination. No person will every wait through any unnecessary segments no matter where they start and end. However, this system requires (n 2 ) segments and will be expensive.

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