|V|·|E| grows faster than |V|³ on sparse graphs and slower on dense ones.

|V|³ is O(|V|·|E|), because a connected graph has at least |V| − 1 edges.

Neither can be compared without knowing the constant factors.

|V|·|E| and |V|³ are always the same order.

|V|·|E| is O(|V|³), because a simple directed graph has at most |V|(|V| − 1) edges.

It is discarded, and only the two outer keys are kept.

It becomes the root of a new subtree below the two new nodes.

It moves down into whichever new node has fewer keys.

It stays in the left of the two new nodes.

It moves up into the parent, which may split in turn, or it becomes a new root, if the node that split was the root.

Θ(n) becomes Θ(√n).

Θ(log n) stays Θ(log n); balancing only speeds up insertion.

Θ(n log n) becomes Θ(n).

Θ(n) becomes Θ(log n).

Θ(log n) becomes Θ(1).

Every vertex in the graph, whether or not the cycle can reach it.

None of them: the distances are still well defined, but Bellman-Ford cannot find them.

Only the vertices on the cycle itself.

Every vertex reachable FROM the cycle, because going round the cycle again always makes the total smaller.

Only the vertices from which the cycle can be reached.

Θ(|E|) for the matrix and Θ(|V|) for the list.

Θ(|V|·|E|) for the matrix and Θ(|E|) for the list.

Θ(|V|²) for the matrix and Θ(|V| + |E|) for the list.

Θ(|V| + |E|) for both.

Θ(|V|²) for both, since both have to be able to represent every possible edge.

Θ(n) for both.

Θ(n²) for the trie and Θ(n) for the tree.

Θ(n log n) for the trie and Θ(n) for the tree.

Θ(n²) for the trie and Θ(n log n) for the tree.

Θ(n²) for both.

It cannot: Θ(n) nodes always means Θ(n) space.

The terminator is copied onto every leaf edge; store it once at the root instead.

The tree can have Θ(n²) edges; store only the branching nodes and drop the leaves.

Each node stores one child pointer per alphabet character; use a hash table at each node instead.

The edge labels together can run to Θ(n²) characters; store each label as a pair of indices into the original string instead of copying it.

Exactly n − 1.

Exactly n.

It depends on how many distinct characters the string uses.

Exactly 2n − 1.

At most n, but usually fewer.

The sides are found by running the algorithm again from t to s and taking the vertices it visits as the source side.

The two sides are the two endpoints of each saturated arc, one side each.

The source side is the set of vertices that can still reach t in the residual network, and the target side is the set of remaining vertices.

The source side is the set of vertices adjacent to s in the original network, and the target side is the set of remaining vertices.

The source side is the set of vertices still reachable from s in the residual network, and the target side is the set of remaining vertices.

The flow is maximum and the cut is minimum.

The network has exactly one maximum flow.

The flow is maximum, but the cut need not be minimum.

The cut is minimum, but the flow need not be maximum.

Nothing: a flow and a cut can have equal value without either being optimal.