Θ(|V|·log |V|)

Θ(|V| + |E|)

Θ(|V|·|E|)

Θ(|E|)

Θ(|V|²)

Every arc leaving s is saturated.

The flow has disconnected the network.

No further INTEGER augmentation exists, though a fractional one might.

The flow is maximum.

Every s-t path contains a saturated arc, but the flow may still not be maximum.

It saves space rather than time, because the suffix tree is smaller than T itself.

Each later pattern can then be matched in Θ(log n) time.

It does not improve on it: each later search still has to look at the whole of T.

Each later pattern can then be matched in Θ(m) time, which does not depend on n.

Each later pattern can then be matched in Θ(1) time, because the tree stores every substring of T explicitly.

At the root, the heights of the two subtrees differ by at most 1.

The height of the whole tree is at most log₂(n).

At every node, the numbers of nodes in its two subtrees differ by at most 1.

Every leaf is at the same depth.

At every node, the heights of its two subtrees differ by at most 1.

|E| ≥ |V|

|V| − 1 ≤ |E| ≤ 2|V|

|V| ≤ |E| ≤ |V|²

|E| ≤ |V| − 1

|V| − 1 ≤ |E| ≤ |V|(|V| − 1)/2

It lets flow travel from the sink back towards the source.

It lets the algorithm detect a negative cycle.

It makes the residual network symmetric, which the algorithm requires.

It records how much capacity the arc (u, v) has left.

It lets a later augmenting path cancel flow an earlier one sent, so the earlier choice can be undone.

A red-black tree has a stricter balance condition, so its lookups are asymptotically faster.

A red-black tree needs fewer rotations than an AVL tree on every individual insertion.

A red-black tree has height Θ(log n) on average, but Θ(n) in the worst case.

A red-black tree permits less strict balance and can be taller; both guarantee Θ(log n) worst-case search time.

Both always produce the same shape for the same insertion order.

One — rebalancing the lowest unbalanced ancestor restores the balance of every ancestor above it as well.

Θ(log n) — one for each level on the path from the new leaf back to the root.

Θ(n) in the worst case, when the tree has degenerated into a chain.

One for each ancestor that is out of balance, and an insertion can leave several out of balance at once.

Two — the lowest unbalanced ancestor, and then its parent.

The edge order was unlucky and the algorithm should be restarted.

The graph has a cycle, which may or may not be negative.

That vertex is unreachable from the source.

The graph has a negative cycle reachable from the source.

Nothing in particular; a decrease on the extra pass is normal.