The overall time taken by this poor merge sort implementation is O(n²).

While the first loop still takes O(n) time, the second loop — which performs the merge — now takes O(n²) time. This is because it repeeatedly removes from the front of the ArrayList, and each removal necessitates shifting all existing elements forward; thus, each iteration of the loop takes O(n) time, and there could be as many as n iterations of this loop. As a result, we can build the following recurrence describing the time for this method.

This recurrence matches the form for the Master Theorem, with a = 2, b = 2, and d = 2. Since log_b a (which is log₂ 2 = 1) is less than d, the Master Theorem says that the solution to this recurrence is O(n²).

    int[] table = new int[n + 1];
    for(int j = 1; j <= n; j++) {
        if(c(1, j) == Integer.MAX_VALUE) {
            int min = Integer.MAX_VALUE;
            for(int k = 1; k < j; k++) {
                int cv = c(k + 1, j);
                if(cv != Integer.MAX_VALUE) {
                    if(table[k] + cv < min) min = table[k] + cv;
                }
            }
            table[j] = min;
        } else {
            table[j] = c(1, j);
        }
    }
    return table[n];
}

Suppose we're given a SET COVER instance consisting of a collection {S₀, S₁, …, S_m − 1} of subsets of some universe V, along with some target number t of subsets to select in order to cover U. We will show how to convert this into a DOMINATING SET problem whose solution solves the original SET COVER problem.

Our corresponding DOMINATING SET graph will have a vertex for each element of the universe U as well as a vertex for each subset S_i and another grandparent vertex. We will have a directed edge from this grandparent vertex to each vertex corresponding to a subset S_i. For each subset S_i, we will also have a directed edge from the subset's vertex to the vertex corresponding to each element of the subset. Our target k for this DOMINATING SET problem will be t + 1 — i.e., one more than for the original SET COVER problem.

We need to show that there is a solution to the SET COVER problem if and only if there is a solution to the constructed DOMINATING SET problem. We first do the only if: Suppose there were a SET COVER consisting of t subsets. We could then select each of the vertices in the DOMINATING SET graph corresponding to one of the selected subsets; this would cover all vertices corresponding to elements of U, since the subsets themselves cover all of U. We will also select the grandparent vertex, which covers itself and all the remaining vertices corresponding to subsets. This covers all vertices in the graph, and so there is a solution to the DOMINATING SET problem using t + 1 vertices.

Now we go in the other direction: Suppose there is a DOMINATING SET solution — does that imply a solution to the original SET COVER problem? First, observe that the DOMINATING SET solution need not include any vertices corresponding to elements from U: If such a vertex is selected, we can unselect it, and instead select a vertex corresponding to a subset containing that element. So we'll assume that no vertices corresponding to U elements are selected. Our solution to SET COVER is then simply to select all those subsets corresponding to vertices selected in the DOMINATING SET solution. The subsets so selected will end up covering all of U, because their corresponding vertices cover all of the vertices corresponding to elements of U. The number of such subsets cannot exceed t, since at most t + 1 vertices are selected, of which one will have to be the grandparent vertex (since there is no other way to cover that vertex), and as we've seen, we can ensure that none of the selected vertices correspond to elements of U. Thus the other t must correspond to subsets.

We define variables f_A, f_B, f_C, and f_D representing the amount (measured in tons) of each customer's shipment placed in the front compartment; c_A, c_B, c_C, and c_D representing the amounts for the center compartment; and r_A, r_B, r_C, and r_D representing the amounts for the rear compartment.

This inequality says that the number of colors required for a valid edge coloring must be at least the graph's maximum degree. Consider the vertex whose degree is maximum: Each edge incident on that vertex must be given a different color, since they all have that vertex in common. Thus we need at least as many colors as there are edges incident to the vertex — which is to say that we need at least as many colors as the degree of the vertex, which we selected so that its degree is Δ(G).

Karger's algorithm is to randomly select an edge in the graph and combine (contract) its two endpoints into a single vertex, merging the edges of the two endpoints together (keeping any duplicate edges so created). We repeat this process until our graph has just two vertices left; the remaining edges are the edges in our candidate cut. This algorithm takes O(n²) time, since each contraction takes O(n) time and there will be n − 2 contractions.

However, this algorithm is not likely to find the minimum cut — the probability that it finds the minimum cut is about ¹/_n². Thus, Karger's algorithm repeats the process of the previous paragraph O(n²) times, so that it is likely to happen upon the true minimum cut. It outputs the smallest cut that it finds among all these attempts.

O(log d). The loop maintains three invariants: First, pp matches p[pid]. Second, d[i] is the distance from i to p[i] in the original tree. And finally, if p[i] is not −1, then d[i] is 2^k, where k is the number of iterations of the loop thus far.

It is easy to see that this holds entering the loop: pp was initialized to p[pid], d[i] was initialized to 1 for everything but the root, and to 0 for the root; that is indeed the distance from node i to the root. And finally, for p[i] is not −1 for all non-root nodes, and for all of those i, d[i] is 1, which matches 2⁰ — and there have been 0 iterations at the beginning.

If the invariant holds at the loop's beginning, it will still hold at the end. The first part about pp matching p[pid] obviously still holds, because the loop's final assignment assures this. The second part holds because dd is computed as the distance from node pid to pp's parent — and by the end of the loop, p[pid] has changed to be the parent of what pp referenced at the iteration's beginning. And finally, if it happens that pp's parent is not −1 (and thus p[pid] is not −1 at the iteration's end), then d[pp] must be 2^k at the loop's beginning, as must be d[pid], so the value of d[pid] must end up being 2 ⋅ 2^k = 2^k + 1. Since k + 1 is the number of iterations completed at the iteration's end, we still have that any entry for which p is not −1, the corresponding entry in d is 2^# iters.

The consequence of this invariant is that each entry in d continues to double until the final iteration. Since no entry in d can exceed d, it follows that the number of iterations must not exceed ⌈log₂ d⌉.

I know of two very different approaches to this problem.

1. In the first, we define a new operator ⊗:

   (θ, x) ⊗ (φ, y) = (θ + φ, sqrt(x² + y² + 2 x y cos φ))

   Essentially, this operator is saying that performing the two commands (θ, x) and (φ, y) is equivalent to turning an angle of θ + φ just once and going a distance of sqrt(x² + y² + 2 x y cos φ)) in that direction.

   We can then perform a parallel scan of the array using this operator, ending up with a final result of (θ_total, d_total). That is the final location in polar coordinates; if we want the location in Cartesian coordinates, we can compute those as (d_total cos θ_total, d_total sin θ_total)

2. The second approach is converts the computation into Cartesian coordinates earlier. We first apply a parallel prefix sum to the first entry of all the pairs, thus converting the turn angles to compass directions. In the example of the problem, our pairs would become: <(45, 40), (75, 50), (180, 40), (270, 20)>.

   Then we convert each pair (φ, d) into (d cos φ, d sin φ), thus getting the change in x-coordinate and change in y-coordinate of each movement. And finally we perform two parallel sums, one for each of the coordinates. We would end up with the total change in x-coordinate and total change in y-coordinate.

Yes, it is in NC. After all, if we were given n⁴ processors   that is a number that is polynomial in n  , then our algorithm takes just O(log² n⁴) = O((4 log n)²) = O(16 log² n) = O(log² n) time, which is polylogarithmic.