1. Frustration sort

1. For the upper bound, observe that each time i resets to 1 the algorithm removes one inversion, and that at most O(n) work occurs between each such removal. Since the initial state of the array as O(n²) inversions, this gives an upper bound of O(n³).

2. For the lower bound, consider an input consisting of 3n/4 ones followed by n/4 zeroes. Each zero must be brought across the 3n/4 ones. For the first n/4 swaps at least, it starts in position n/2 or greater. So we have a cost of at least (n/4 zeroes) * (n/4 swaps) * (n/2 comparisons) = Omega(n³).

2. Triathlon routing

Here is an algorithm that calls DepthFirstSearch once on a newly-constructed graph. Given the input graph G = (V,E), construct a new graph G' with vertices of the form v_i where v is a vertex of G and i is 1, 2, or 3, depending on how many different modes of locomotion have been used to reach v. Let the edges of G' consist of

• An edge (v₁,v₂) and an edge (v₂,v₃) for each v in V.

• An edge (u₁,v₁) for each swimmable edge uv in E, (u₂,v₂) for each bikable edge uv in E, and (u₃,v₃) for each runnable edge uv in E.

Now run DepthFirstSearch on G' starting at s₁ and return all nodes v for which v₃ is reachable in G'.

Observe first that any path through G' consists of swimmable edges, bikable edges, and runnable edges, joined by two utility edges (v₁,v₂) and (v'₂,v'₃). So the reachable v₃ nodes in G' correspond precisely to the nodes of G reachable by permitted paths.

To compute the running time, observe that G' has exactly 3|V| vertices and up to 2|V|+3|E| edges. So DepthFirstSearch takes O(3|V| + 2|V| + 3|E|) = O(|V|+|E|) time. The cost of constructing the graph should be the same; we just have to loop over all vertices and edges in G and spit out a constant number corresponding vertices or edges of G' for each. We can't expect to do better than this (as DepthFirstSearch reduces to this problem by labelling all edges as swimmable only), so in fact we have a Theta(|V|+|E|) algorithm.