MATH 182: Algorithms

Spring 2026, W. Adkisson

Please let me know at kennyguo@ucla.edu if you spot any errors. Thanks!

Homework Solutions: (in progress)

Homework 1 (time complexity)
Homework 2 (greedy algorithms)
Homework 3 (divide and conquer)
Homework 4 (dynamic programming, graph algorithms)
Homework 5 (BFS, DFS, Dijkstra, Prim)
Homework 6 (network flow)

Homework 1

Question 1: Big O

Prove that for any functions \(f, g : \mathbb{N} \to \mathbb{R}_{\ge 0}\) and any real number \(a > 0\), if \(f(n) \in O(g(n))\) then \(f(n)^a \in O(g(n)^a).\)

Prove that \[\log(n!) \in \Theta(n \log n).\]

Prove that \(n^{\log n}\) is not in \(O(p(n))\) for any polynomial \(p(n)\).

Proof.

By definition, we have that there exists some \(c > 0, N \in \mathbb{N}\) such that for all \(n > N\), \(f(n) \leq c\cdot g(n).\) Since \(a > 0\), exponentiation by \(a\) is monotone increasing on \(\mathbb{R}_{\geq 0}\), so pick \(c' = c^a\) and we have that for all \(n > N\), \((f(n))^a \leq c' \cdot (g(n))^a\). \(\square\)
By log properties, we have that \(\log(n!) = \sum_{i=1}^n \log(i).\) Since log is monotone increasing, we can plug in \(i = n\) for all \(i\) to get the upper bound \[ \log(n!) \leq n \log(n) \] so \(\log(n!) \in O(n \log n).\) Furthermore, WLOG, assume \(n\) is divisible by \(2\), and write \[\begin{align*} \sum_{i=1}^n \log(i) &= \log(1) + \log(2) + \ldots + \log(n/2) + \ldots + \log(n) \\ &\geq \log(n/2) + \log(n/2 + 1) + \ldots + \log(n) \\ &\geq (n/2+1)\log(n/2), \end{align*}\] where the first inequality follows from noting that \(\log(x) \geq 0\) for \(x \geq 1\), and the second inequality follows from the monotonicity of log. Suppressing lower-order terms and constants, we attain the lower bound \(\log(n!) \in \Omega(n \log n)\). Thus, \(\log(n!) \in \Theta(n \log n)\).
We can without loss of generality consider just the maximum degree of any \(p(n)\). Suppose that \(n^{\log n}\) is \(O(n^d)\) for some \(d \in \mathbb{N}\), i.e., there is some \(C >0, N \in \mathbb{N}\) s.t. for all \(n > N\), \(n^{\log n} \leq C \dot n^d\), or equivalently, \(n^{\log (n)- d} \leq C\). Thus, clearly picking \(n > n_0\) such that \(n_0 > C\) and \(\log(n_0) > d + 1\) contradicts this.

Question 2: Algorithm Runtimes

For each algorithm below, find a function \(f(n)\) such that the algorithm runs in time \(\Theta(f(n))\). You should explain the reasoning behind your answer but you do not need to give a formal proof. For partial credit, you may find a function \(f(n)\) so that the algorithm’s running time is \(O(f(n))\) (i.e. \(f\) is an upper bound for the running time, but not necessarily a tight upper bound).

Algorithm 1
Foo(n):
    if n > 1:
        Foo(n - 1)
        Foo(n - 1)
Algorithm 2
Bar(n):
    x = 0
    for i = 1, 2, ..., n:
        x = x + i
    while x > 0:
        x = x - 2
Algorithm 3
Baz(n):
    while n > 1:
        n = floor(n / 2)
        Baz(n)

Answer.

This algorithm is \(\Theta(2^n)\). The recursion produces \(n\) total layers, with \(2^i\) recursive calls for each layer \(i\). Each call performs constant work (comparison to \(1\), function calls, etc.). Thus the total work is proportional to \(1 + 2 + 4 + \ldots 2^n\), which by the geometric sum formula, is \(\Theta(2^n)\).
This algorithm is \(\Theta(n^2)\). Intialization of \(x\) is constant time. Each iteration of the for-loop is constant work, but it iterates \(n\) times, resulting in \(\Theta(n)\) time. \(x\) is now equal to \(n(n+1)/2\). The while loop subtracts \(2\) from \(x\) every iteration (constant work), and it will terminate when \(x\) becomes non-positive. We can approximate the number of iterations it will perform by dividing \(x\) by \(2\); approximately \(n(n+1)/4\) iterations, or \(\Theta(n^2)\) time. This latter term dominates.
This algorithm is \(\Theta(n)\). Assuming WLOG that \(n = 2^k\) for some integer \(k\), We can write out the time recursion as \[ T(n) = T(n/2) + T(n/4) + \ldots + T(1) + O(\log n), \] since Baz performs constant work each iteration of the while loop and calls \(\log n\) separate times. If we redefine \(S(k) = T(2^k)\), we can write out another recursion \[ S(k) = S(k-1) + S(k-2) + S(0) + O(k). \] Looking at \(k-1\): \[ S(k-1) = S(k-2) + S(0) + O(k-1) \] and subtracting this from the first, we can obtain \[ S(k) = 2S(k-1) + O(1) \] which is equivalent to a function that performs constant work, has 2 recursive calls each call, and has \(k\) layers. This is the same as algorithm \(1\), so the runtime is \(\Theta(2^k) = \Theta(n)\) runtime.

Question 3: Algorithm Correctness Two algorithms are shown below. Each one is supposed to take an array of integers, \(A\), and sort it in increasing order. For each algorithm, determine whether or not the algorithm is correct. If it is, prove it. If it is not, give an example of an input on which the algorithm does not work correctly.

Sorting algorithm 1
Sort(A):
    for i = 1, 2, ..., n:
        for j = 1, 2, ..., n:
            if A[i] < A[j]:
                swap A[i] and A[j]

Proof.

This algorithm is correct.

We show the loop invariant for the outer loop: after iteration \(i\), the first \(i\) elements in \(A\) are sorted in increasing order. The base case for \(i = 1\) is obvious, since there are no elements to its left.

Now assume the loop invariant is true for \(i-1\). For the inner loop (j):

First consider the case where there is some index \(j < i\) such that \(A[i] < A[j]\), and assume this is the first \(j\) encountered starting from the beginning (\(j=1\)), so the algorithm swaps \(A[j]\) and \(A[i]\). It must hold that \(A[1], \ldots, A[j-1]\) are sorted (by the inductive hypothesis) and \(A[1], \ldots, A[j-1] \leq A[j]\) (by the condition for swapping having failed). Furthermore, by the inductive hypothesis, the element now given by \(A[i]\) was weakly less than the element \(A[j+1]\), which is weakly less than that in \(A[j+2]\), and so on up to \(A[i-1]\). Thus, in any case where this inequality is strict, the algorithm will swap, and thus sort the remaining elements up to index \(i\). Finally, for \(j = i+1, \ldots n\), note that the algorithm will only perform the swap if \(A[j] > A[i]\), and since \(A[i]\) was already larger than all elements before, after the swap, \(A[i]\) will still be larger. Hence, the first \(i\) elements are sorted.
1. Now consider the case where there is no index \(j \leq i\) such that \(A[i] < A[j]\). Thus, \(A[i] \geq A[i-1]\), and the first \(i\) elements are sorted. After iterating through \(j = i+1, \ldots, n\), by the same reasoning as before, the first \(i\) elements will still be sorted.
Finally, since for loops always terminate, we close the induction, and in particular, considering the case where \(i = n\), we have that \(A\) is sorted after the algorithm returns.

Sorting algorithm 2

Sort(A):
    for i = 1, 2, ..., n:
        for j = 1, 2, ..., n - i:
            if A[j] > A[j + 1]:
                swap A[j] and A[j + 1]

Proof.

This algorithm (Bubble Sort) is correct.

We first show the loop invariant for the inner loop (\(j\)) that after iteration \(j\), the \((j+1)\)-th element of \(A\) is the largest within the subarray \(A[1:j+1]\). The base case for \(j=1\) is obvious after a simple comparison between \(A[1]\) and \(A[2]\). Now assume the loop invariant holds for \(j-1\). If \(A[j+1] \geq A[j]\), then no swap occurs, and \(A[j+1]\) is also larger than all previous elements by the IH. If the opposite, then the swap occurs, and again by the IH, \(A[j+1]\) is still larger than all previous. Finally, we have that the inner for loop is finite and thus terminates, closing the induction. Applying this to the case for \(j = n-i\), we have that \(A[n-i+1]\) is the largest element in the subarray \(A[1:n-i+1]\).

We use this to show the loop invariant for the outer loop (\(i\)) that after iteration \(i\), the last \(i\) elements are the largest elements in \(A\), and sorted. The base case is clear for \(i = 1\), using the inner for loop, we have that the last element is the largest element. Now assume that the loop invariant holds for some \(i\), i.e., \(A[n-i+1:n]\) are the \(i\) largest elements and sorted. Applying the inner loop conclusion, we have that after iteration \(i\), \(A[n-i]\) is the largest element within \(A[1:n-i]\), and by the IH, less than or equal to \(A[n-i+1]\). Thus, the subarray \(A[n-i:n]\) are the \(i+1\) largest elements of \(A\) and sorted. The loop terminates since it’s a for loop, and we conclude for the case when \(i=n\) that \(A\)’s elements are sorted (and the largest \(n\) elements).

Question 4: Matrix Rows

Suppose you are given an \(n \times n\) matrix of 0’s and 1’s in which all the 0’s in a row come at the end (in other words, each row consists of a sequence of all 1’s followed by a sequence of all 0’s). You want to find which row of the matrix has the most 1’s (if there are multiple rows tied for the most 1’s you may output any row with the maximal number of 1’s). Find an \(O(n)\) time algorithm to solve this problem. You may assume that the matrix is given as a 2-dimensional array \(A\) and that \(A[i][j]\) will give you the element in the \(i\)th row and \(j\)th column of \(A\) in \(O(1)\) time.

Answer.

FindRow(A):
    i = 1
    j = 1
    best_row = 1
    while true:
        if A[i][j] == 1:
            if j < n:
                j++
            else:
                return best_row
        else:
            while A[i][j] == 0:
                if i < n:
                    i++
                else:
                    return best_row
            best_row = i
            continue
    return

This algorithm runs in linear time, because it only makes either downward moves or rightward moves. Since there are at most \(n\) possible moves in either direction, and for every move, the algorithm does constant work (checks the element, increments counter, checks if at boundary), this is linear time.

Question 5: Challenge Problem: Matrix of Sums

Suppose you are given an array \(A\) of \(n\) integers. You want to find an \(n \times n\) array \(B\) in which \(B[i][j]\) (for \(i < j\)) is the sum of array entries \(A[i]\) through \(A[j]\) inclusive; we don’t care what \(B[i][j]\) is when \(j < i\). That is, for \(i < j\), we want \[B[i][j] = A[i] + A[i+1] + \cdots + A[j].\]

Analyze the runtime of the following algorithm for this problem:
MatrixSums(A):
    for i = 1, ..., n:
        for j = i+1, ..., n:
            Add array entries A[i] through A[j]
            Store the result in B[i][j]
That is, find a function \(f\) such that the runtime for this algorithm is \(\Theta(f(n))\).

This algorithm is the most straightforward approach: for each pair \((i,j)\), it simply computes the relevant entry. It is also quite inefficient. Give an algorithm with asymptotically better runtime. That is, design an algorithm with runtime \(O(g(n))\), where \[\lim_{n \to \infty} \frac{g(n)}{f(n)} = 0.\]

Answer.

Adding array entries \(A[i]\) through \(A[j]\) each time takes on average \(O(n)\) time (this is a large inefficiency). Storing the result is constant time. Finally, since this all takes place within a double nested for loop over \(n\), the time cost is multiplied by \(O(n^2)\) for a total time complexity of \(O(n^3)\).

This algorithm first initializes the first row of \(B\) (\(O(n^2)\)) time and then uses the previous rows to construct the succeeding rows by simply taking the entry above and subtracting the element in A corresponding to the previous row. This is still a double nested for loop, but each iteration takes constant time, for a time complexity of \(O(n^2)\). Thus, the total time complexity is \(O(n^2)\).

Homework 2

Homework 3

Homework 4

Homework 5

Homework 6