Suppose we have a list of N world cities, numbered from 0 to N-1. The two-dimensional array of doubles dist holds the airline distance between each pair of cities: dist[i][j] is the distance between city i and city j.

Now, for every pair of cities i and j, we'd like to consider all the flights between the two that make one stop in a third city k, and record which city k yields the shortest distance traveled in a one-stop flight between city i and city j that passes through city k. Here's the code:

 const int N = some value; assert(N > 2); // algorithm fails if N <= 2 double dist[N][N]; ... int bestMidPoint[N][N]; for (int i = 0; i < N; i++) { bestMidPoint[i][i] = -1; // one-stop trip to self is silly for (int j = 0; j < N; j++) { if (i == j) continue; int minDist = maximum possible integer; for (int k = 0; k < N; k++) { if (k == i || k == j) continue; int d = dist[i][k] + dist[k][j]; if (d < minDist) { minDist = d; bestMidPoint[i][j] = k; } } } } 

What is the time complexity of this algorithm, in terms of the number of basic operations (e.g., additions, assignments, comparisons) performed: Is it O(N), O(N log N), or what? Why? (Note: In this homework, whenever we ask for the time complexity, we care only about the high order term, so don't give us answers like O(N²+4N).)

The algorithm in part a doesn't take advantage of the symmetry of distances: for every pair of cities i and j, dist[i][j] == dist[j][i]. We can skip a lot of operations and compute the best midpoints more quickly with this algorithm:

 const int N = some value; assert(N > 2); // algorithm fails if N <= 2 double dist[N][N]; ... int bestMidPoint[N][N]; for (int i = 0; i < N; i++) { bestMidPoint[i][i] = -1; // one-stop trip to self is silly for (int j = 0; j < i; j++) // loop limit is now i, not N { int minDist = maximum possible integer; for (int k = 0; k < N; k++) { if (k == i || k == j) continue; int d = dist[i][k] + dist[k][j]; if (d < minDist) { minDist = d; bestMidPoint[i][j] = k; bestMidPoint[j][i] = k; } } } } 

What is the time complexity of this algorithm? Why?