Due: January 30, 23:59 Atlantic time, in Crowdmark.

Note that the substitution method is a specific style of induction proof, discussed in the textbook and in class.

Prove that the running time of the Peasant Multiply algorithm¹ is \(\Theta(n²)\). It’s important to note that if \(n\) is the number of bits in the input, and in this model we pay \(\Theta(n)\) cost to add two \(n\) bit integers (and to divide an \(n\) bit integer by 2). For a pseudocode version, see the link above.

def PeasantMultiply(x,y):
    prod = 0
    while x>0:
        if x%2 == 1:
            prod = prod + y
        x = x//2
        y = y + y

    return prod

if __name__ == "__main__":
    from random import randrange
    x=randrange(0,100)
    y=randrange(0,100)
    print(f"x={x} y={y} x*y={PeasantMultiply(x,y)}")

For each of the following recursion relations, if it can be solved by the master theorem, solve it, otherwise explain why the master theorem can not be used.

• \(T(n) = 2T(n/3) + 1\)
• \(T(n) = 1.5T(n/3) + \sqrt(n)\)
• \(T(n) = T(log(n)) + 1\)
• \(T(n) = 8T(n/2) + n³ +101n² - 3n\)

Suppose \(T(n) = T(n/2) + \lg(n)\). Use the substitution method (induction) to show

\(T(n) ∈ O( (\lg n)²)\)

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

\(T(n) ∈ O(n)\)