Sample Questions

Asymptotics

Prove the following asymptotic bounds:

• ∀ a>1 an ∈ O(nᵃ)
• ∀ a>0, b > 0, nᵃ+nᵇ ∈ O(nᶜ) where c=a+b

Recurrences

example 1

Let T (n) = T (n/4) + T (n/2) + Θ(n). Prove by substitution that

T (n) ∈ O(n)

example 2

Let T(n) = T(n/6) + T(4n/5) + cn^2. Show that T(n) ∈ O(n^2)

example 3

Find (and prove) a summation equivalent to

T(n) = T(n-1) + nᶜ

example 4

Solve the following recurrence

T(n) = T(n-1) + cⁿ

Divide and Conquer

Binary Multiplication

In the following, suppose x and y are two n bit numbers, where n = 2ᵏ for some integer k. The function shiftl(a, b) returns 2ᵇ × a, and takes Θ(log b) time. The function plus(a, b) returns a + b and takes Θ(log a + log b) time (i.e. plus(x, y) would take Θ(n) time). Analyze the complexity of the following algorithm.

function Mult(x, y)
    Let n = bits(x) = bits(y)
    if n=1 return x*y
    Let xL (yL ) be the left n/2 bits of x (y).
    Let xR (yR) be the right n/2 bits of x (y).
    z ← shiftl(Mult(xL , yL ), n)
    z ← plus(z, shiftl(plus(Mult(xL , yR ), Mult(xR , yL )), n/2 ))
    z ← plus(z, Mult(xR , yR ))
    return z
end function

Array append

Consider the following recursive algorithm to append two arrays.

    function Append(A[̣1…k], B[1…l])
        if k = 0 return B
        if l = 0 return A
        C = Append(A[1 . . . k], B[1 . . . l − 1])
        return C ◦ B[l]
    end function

The symbol ◦ represents the operation of appending one element to an array. Analyze this algorithm under the assumption that for an array S of size p and element e, the cost of computing S ◦ e is

• Θ(1)
• Θ(p)