How would we use the graph algorithm to justify this runtime of 0(n^2)?

Question

A city consists of a set of n bus stops. There are two main bus lines in the city: the red bus line and the blue bus line. Buses travel between pairs of bus stops. Two bus stops may be connected by either the red bus, the blue bus, both buses, or neither bus. You would like to travel from bus stop X to bus stop Y. You have enough money for one bus ticket, and the bus ticket includes exactly one transfer between bus lines. That means you can leave X on the blue line, and transfer at some point to the red line until you reach Y , or you could travel the entire route on the same bus line, or you can start on the red bus line and then transfer to blue. Your job is to design an algorithm that determines if there is a way for you to get from X to Y using your one ticket. Justify the runtime of O(n^2).

Answer 1

Here is my rough pseudocode to solve this. It requires some dynamic programming (https://en.wikipedia.org/wiki/Dynamic_programming).

func find_path(Stop start, Stop dest) -> boolean

return helper(start, stop, blue, false) && helper(start, stop, red, false)

func helper(Stop current, Stop dest, BusLine currentLine, boolean hasTransferred) -> boolean

if current == dest:

return true // found it!!!

else if current == null:

return false // this is a dead end :(

else:

// Can we get to the destination by staying on the current line?

boolean stayOnCurrentLine = helper(currentLine.nextStop(current), dest, currentLine, hasTransferred)

// Can we even transfer to the other line?

boolean canTransfer = !hasTransferred && containsStop(otherLine(currentLine), current)

// Can we get to the destination by transferring to the other line?

boolean transferLine = canTransfer && helper(nextStop(otherLine(currentLine), current), dest, otherLine(currentLine), true)

return stayOnCurrentLine && transferLine

/* Functions of bus lines and bus stops that I assume we are provided with */

// returns the other bus line (use for transfers)

func otherLine(BusLine line) -> BusLine

// returns if a stop is present on this particular line

func containsStop(BusLine line, Stop stop) -> Bool

// returns the next stop aft

To justify O(n^2), we should first imagine if we just had 1 bus line. If we went from one end of the line to the other, we'd be traversing all n stops, which gives us a runtime of O(n). However, since we get one transfer opportunity, we have to take that into account at every step. Let's say we transfer at the first stop. Then we'd essentially be traversing each line twice, or O(2n). But we can also transfer at the second stop. If we did that, it'll be O(3n). And so on and so forth, up to transferring at the nth stop, which, in total, gives us O(n^2).

Of course, this would be much easier to visualize and understand if we could walk through it step-by-step. So if this is unclear or you need more help, I am happy to walk through it with you! Just book a session with me and I will walk through it and explain it until you understand. Right now I am still offering heavily discounted price because I am new to this Wyzant (but not new to tutoring!). Eventually, I will raise it to my regular rate, so book soon!