Algorithm II - Hoang Anh Duc - MIM - HUS - VNU

Work 1.

$$\begin{align} & \text{Give a Big-O estimate of the following recurrence} \quad \\[5pt] & \text{relations using the Master Theorem, given } T(1) = 1 \quad \\[5pt] & (1) \quad T(n) = 4T(n/3) + n^2 \quad \\[5pt] & (2) \quad T(n) = 4T(n/2) + n^2 \quad \\[5pt] & (3) \quad T(n) = 3T(n/3) + n \quad \\[5pt] & (4) \quad T(n) = 3T(n/3) + 1 \quad \end{align}$$

Block

• Solution:

$$\begin{align} & T(n) = 4T(n/3) + n^2 \quad \\[5pt] & \text{Here, } a = 4, b = 3, d = 2 \quad \\[5pt] & \log_b a = \log_3 4 \approx 1.2619 \quad \\[5pt] & d = 2 \quad \\[5pt] & \log_b a < d \implies T(n) = \Theta(n^d) = \Theta(n^2) \end{align}$$

Block

$$\begin{align} & T(n) = 4T(n/2) + n^2 \quad \\[5pt] & \text{Here, } a = 4, b = 2, d = 2 \quad \\[5pt] & \log_b a = \log_2 4 = 2 \quad \\[5pt] & \log_b a = d \implies T(n) = \Theta(n^d \log n) = \Theta(n^2 \log n) \end{align}$$

Block

$$\begin{align} & T(n) = 3T(n/3) + n \quad \\[5pt] & \text{Here, } a = 3, b = 3, d = 1 \quad \\[5pt] & \log_b a = \log_3 3 = 1 \quad \\[5pt] & \log_b a = d \implies T(n) = \Theta(n^d \log n) = \Theta(n \log n) \end{align}$$

Block

$$\begin{align} & T(n) = 3T(n/3) + 1 \quad \\[5pt] & \text{Here, } a = 3, b = 3, d = 0 \quad \\[5pt] & \log_b a = \log_3 3 = 1 \quad \\[5pt] & \log_b a > d \implies T(n) = \Theta(n^{\log_b a}) = \Theta(n) \end{align}$$

Block

Work 2.

$$\begin{align} & \text{Estimate of the following recurrence} \quad \\[5pt] & \text{relations T(n) using the Recursion Tree:} \quad \\[5pt] & (1) \quad T(n) = 2T(n/2) + n^2 \quad \\[5pt] & (2) \quad T(n) = T(n/2) + 1 \quad \\[5pt] & (3) \quad T(n) = 2T(n - 1) + 1 \quad \end{align}$$

Block

• Solution:

$$\begin{align} & T(n) = 2T(n/2) + n^2 \quad \\[5pt] & \text{At level 0, the cost is } n^2 \quad \\[5pt] & \text{At level 1, the cost is } 2 \cdot \left(\frac{n}{2}\right)^2 = \frac{n^2}{2} \quad \\[5pt] & \text{At level 2, the cost is } 4 \cdot \left(\frac{n}{4}\right)^2 = \frac{n^2}{4} \quad \\[5pt] & \text{Summing up, we get a geometric series with} \quad \\[5pt] & \text{total cost } n^2 \times \sum_{i=0}^{\log n} \frac{1}{2^i} = O(n^2) \quad \end{align}$$

Block

$$\begin{align} & T(n) = T(n/2) + 1 \quad \\[5pt] & \text{At level 0, the cost is } 1 \quad \\[5pt] & \text{At level 1, the cost is } 1 \quad \\[5pt] & \text{At level 2, the cost is } 1 \quad \\[5pt] & \text{There are } \log n \text{ levels, so the} \quad \\[5pt] & \text{total cost is } O(\log n) \quad \end{align}$$

Block

$$\begin{align} & T(n) = 2T(n-1) + 1 \quad \\[5pt] & \text{At level 0, the cost is } 1 \quad \\[5pt] & \text{At level 1, the cost is } 2 \quad \\[5pt] & \text{At level 2, the cost is } 4 \quad \\[5pt] & \text{At each level, the cost doubles, } \quad \\[5pt] & \text{and there are } n \text{ levels, so the total cost is } O(2^n) \quad \end{align}$$

Block

Work 5.

• Given algorithm:

# input: a: real number != 0, n: non-negative int
# output: a^n

procedure power(a, n):
    if n = 0 then
        return 1
    else
        return a * power(a, n - 1)

• (a) Prove the correctness of algorithm above.

• (b) Construct a recurrence relation to evaluate the running time of algorithm above. Solve or estimate the recurrence relation you found.

• Solution:

$$\begin{align} & \text{We need to prove that the algorithm correctly computes } a^n \quad \\[5pt] & \text{We use mathematical induction on } n \quad \\[5pt] & \textbf{Base case:} \quad n = 0 \quad \\[5pt] & \text{The algorithm returns } 1, \text{ which is correct because } a^0 = 1 \quad \\[5pt] & \textbf{Inductive step:} \quad \text{Assume the algorithm correctly computes } a^k \text{ for } k < n \quad \\[5pt] & \text{For } n, \text{ the algorithm computes } a * power(a, n - 1) \quad \\[5pt] & \text{By the inductive hypothesis, } power(a, n - 1) = a^{n - 1}, \text{ so the result is } a * a^{n-1} = a^n \quad \\[5pt] & \text{Thus, by induction, the algorithm correctly computes } a^n \end{align}$$

Block

$$\begin{align} & \text{Let } T(n) \text{ be the time complexity of the algorithm for input size } n \quad \\[5pt] & \text{The algorithm makes a recursive call to } power(a, n - 1), \text{ so the recurrence is:} \quad \\[5pt] & T(n) = T(n-1) + O(1) \quad \\[5pt] & \text{This recurrence has a linear form. We solve it by expanding:} \quad \\[5pt] & T(n) = T(n-1) + O(1) = T(n-2) + O(1) + O(1) = \dots = T(0) + O(n) = O(n) \quad \\[5pt] & \text{Therefore, the time complexity of the algorithm is } O(n) \end{align}$$

Block

Work 6.

• Given algorithm:

# input: a_1, a_2, ... , a_n: int sequence; i, j, x: int; 1 <= i <= j <= n
# output: if x in {a_i, a_{i+1}, ... , a_j} then return k in {i, i+1, ... , j}
# such that x = a_k; otherwise return 0

procedure linear_search(i, j, x):
    if a_i = x then     # correct position? return
        return i
    else
        if i = j then   # not found
            return 0
        else            # found in rest of sequence
            return linear_search(i + 1, j, x)

• Construct a recurrence relation to evaluate the running time of algorithm above. Solve or estimate the recurrence relation you found.

• Solution:

$$\begin{align} & \text{Let } T(i, j) \text{ represent the running time of the linear search algorithm.} \quad \\[5pt] & \text{The algorithm makes a recursive call to } linear\_search(i+1, j, x) \text{ at each step, so:} \quad \\[5pt] & T(i, j) = T(i+1, j) + O(1) \quad \\[5pt] & \text{This recurrence keeps reducing the size of the search by one until } i = j, \text{ so:} \quad \\[5pt] & T(i, j) = T(i+1, j) + O(1) = T(i+2, j) + O(1) + O(1) = \dots = T(j, j) + O(j - i + 1) = O(j - i + 1) \quad \\[5pt] & \text{Thus, the time complexity for the worst case (where the search proceeds to the end) is } O(j - i + 1) \quad \\[5pt] & \text{If the entire array is searched (from index 1 to n), the time complexity is } O(n) \end{align}$$

Block

Work 7.

• Given algorithm:

# input: a_1, a_2, ... , a_n: int sequence; i, j, x: int; 1 <= i <= j <= n
# output: if x in {a_i, a_{i+1}, ... , a_j} then return k in {i, i+1, ... , j}
# such that x = a_k; otherwise return 0

procedure binary_search(i, j, x):
    m := floor((i + j) / 2)
    if x = a_m  then
        return m
    else
        if x < a_m & i < m then
            return binary_search(i, m - 1, x)
        else 
            if x > a_m & j > m then
                return binary_search(m + 1, j, x)
            else
                return 0

• Construct a recurrence relation to evaluate the running time of algorithm above. Solve or estimate the recurrence relation you found.

• Solution:

$$\begin{align} & \text{Let } T(n) \text{ represent the running time of binary search on an array of size } n \quad \\[5pt] & \text{Each recursive call divides the search interval in half, reducing the size by } n/2 \text{ at each step.} \quad \\[5pt] & \text{Thus, the recurrence relation is:} \quad \\[5pt] & T(n) = T\left(\frac{n}{2}\right) + O(1) \quad \\[5pt] & \text{To solve the recurrence, we expand it as follows:} \quad \\[5pt] & T(n) = T\left(\frac{n}{2}\right) + O(1) = T\left(\frac{n}{4}\right) + O(1) + O(1) = \dots = T(1) + O(\log n) \quad \\[5pt] & \text{Since } T(1) = O(1), \quad T(n) = O(\log n) \quad \\[5pt] & \text{Thus, the time complexity of binary search is } O(\log n) \end{align}$$

Block