Mock midterm A (exam mode)

(a) $5 + 4\log_2 n$.

(b) $4\cdot\frac{n(n+1)}{2} + n = 2n^2 + 3n$.

(c) $\frac{3^5 - 1}{3 - 1} = \frac{242}{2} = 121$.

(a) The j loop runs $n - i + 1$ times, so the total is $10\sum_{i=1}^n (n - i + 1) = 10\cdot\frac{n(n+1)}{2} = 5n(n+1)$.

(b) $\Theta(n^2)$. The k loop is a constant (10) factor, so it doesn't change the growth rate.

(a) Upper: for $n \ge 1$, $6n^2 + 4n - 10 \le 6n^2 + 4n^2 = 10n^2$, so $c_2 = 10$. Lower: $6n^2 + 4n - 10 \ge 6n^2$ when $4n \ge 10$, i.e. $n \ge 3$, so $c_1 = 6$. Take $n_0 = 3$. Check $n = 3$: $54 \le 56 \le 90$ ✓

(b) $\log(n^2) = 2\log n < \sqrt n < n\log n < n^{1.5} < 2^{n/2}$.

(a) $j = 2$: [2, 6, 8, 1, 4] (1) · $j = 3$: [2, 6, 8, 1, 4] (0) · $j = 4$: [1, 2, 6, 8, 4] (3) · $j = 5$: [1, 2, 4, 6, 8] (2). 6 shifts.

(b) At the start of each iteration, A[1..j-1] holds the original first $j - 1$ elements in sorted order. Maintenance: elements bigger than the key shift right by one, keeping their order, and the key drops into the gap after the last element ≤ key, so A[1..j] is sorted.

Invariant: at the start of iteration $i$, $c$ = the number of even elements in $A[1..i-1]$. Init: $i = 1$, the range is empty, and $c = 0$ ✓. Maintenance: if $A[i]$ is even, $c$ goes up by 1, otherwise it is unchanged, so $c$ counts the evens in $A[1..i]$ ✓. Termination: the loop exits at $i = n + 1$, so $c$ = the number of evens in $A[1..n]$ ∎

Base $n = 1$: LHS $= 2$, RHS $= 0 + 2 = 2$ ✓. Step: assume it holds for $k$. Then $\sum_{i=1}^{k+1} i2^i = (k-1)2^{k+1} + 2 + (k+1)2^{k+1} = 2k\cdot2^{k+1} + 2 = k\cdot2^{k+2} + 2$, which is the formula with $n = k + 1$ ✓ ∎

(a) 2, 3, 4, 5, 9, 10, 11. Comparisons: 3v2, 3v4, 5v4, 5v10, 9v10, then the left list is empty: 5.

(b) Level $i$: $3^i$ nodes of size $n/2^i$, total $(3/2)^i n$, which grows. The leaves dominate: $3^{\log_2 n} = n^{\log_2 3} \approx n^{1.585}$, so $\Theta(n^{\log_2 3})$.

(c) One node per level, $\log_3 n + 1$ levels, so $\Theta(\log n)$.