DSA2 Quizzes 3 & 4 RUNTIMES

Prim's MST Algorithm

E number of edges.
O(|E| log|V|) = extractMin() + decreaseKey() = O(|V| log|V| + |E| log|V|)

Kruskol’s MST Algorithm

O(|E| log|E|)

E number of edges.

Factor of E from sorting all edges.

O(log|E|) from Union-Find.

Log Cutting

O(n²)

n is the length of the log.

Nested for loops. Outer loop iterating through log size, inner loop iterating through last cut size.

Matrix Chaining

Θ(n³) = Θ(n²) * Θ(n)

n number of matrices

Θ(n²) subproblems to solve, corresponding to number of ways to divide the chain of matrices into two subchains.

Θ(n), each problem can be solved in Θ(n) time.

Making Change (DP)

O(kn)
k number of coins, n is the amount to make change for.
There are k * n subproblems, each solved in constant time.

Seam Carving

Θ(n*m)

n number of rows and m number of columns.

Θ(1) to calculate energy of each pixel, total of Θ(nm). Θ(nm) using DP to find minimum energy seam.

Largest Common Subsequence

Θ(n*m)

|X| = n and |Y| = m, where n and m are the lengths of the two strings.

m*n subproblems, each solved in constant time by looking up solution in table.

Gerrymandering

Θ(n⁴m²)
n number of precincts and m number of votes.

4 nested for loops. Outer-most iterates first j precincts until n total precincts, then iterates k precincts until min(j, n/2), then iterates x voters for a party in D₁ until j*m, inner-most iterates y voters for a party in D₂ until j*m.

Interval Scheduling (w/o sorting)

Θ(n)