Analysis of Algorithms
Homework 2
Arthur Nunes-Harwitt
F0 = 0
F1 = 1
Fn = Fn−1 + Fn−2
f(0; a, b) = a
f(1; a, b) = b
f(n; a, b) = f(n− 1; b, a+ b)
Theorem 1 For any n ∈ N if n > 1 then f(n; a, b) = f(n− 1; a, b) + f(n− 2; a, b).
Theorem 2 For any n ∈ N, Fn = f(n; 0, 1).
Theorem 3 For any n ∈ N, Fn = 1√5 (ϕn − ϕˆn), where ϕ = 1+
√
5
2 and ϕˆ =
1−√5
2 .
1. The function fib implemented the recurrence Fn. We can characterize the time taken by fib in terms of
the number of additions (plusses) performed. We can write a recurrence TF (n) that computes this number as
follows. Observe that there are no additions performed for the base cases. Hence TF (0) = 0 and TF (1) = 0.
Also observe that the number of additions to compute Fn is one more than the number of additions to compute
Fn−1 together with the number of additions to compute Fn−2. Hence TF (n) = 1 + TF (n − 1) + TF (n − 2).
Putting this together, we have the following recurrence.
TF (0) = 0
TF (1) = 0
TF (n) = 1 + TF (n− 1) + TF (n− 2)
It turns out that for any n ∈ N, TF (n) = Fn+1 − 1. Use limits together with theorem 3 to show that TF (n) ∈
Θ(ϕn).
2. The function fibItHelper implemented the recurrence f(n; a, b). What is the time complexity of fibItHelper?
Write down a recurrence relation Tf (n) that characterizes the time complexity in terms of the number of addi-
tions (plusses) performed; then solve the recurrence exactly using iteration.
3. Notice that f is repeatedly operating on the numbers a and b.
LetL : N2 → N2 be defined byL(a, b) = (b, a+b). Then f(n; a, b) can be understood as (Ln(a, b))1. Prove this
assertion by using mathematical induction to prove that for any n ∈ N, Ln(a, b) = (f(n; a, b), f(n+ 1; a, b)).
1
4. (project) Write a function fibPow that takes a natural number n, and returns (Ln(0, 1))1.
(a) First choose a representation for L. (HINT: The variable L is used because the function is a linear operator.
Functional programmers beware!)
(b) Then implement an algorithm to raise objects of that type to the nth power that requires only O(log(n))
“iterations.”
(c) Finally, implement fibPow using the representation of L and the power algorithm.
(d) What is the asymptotic time complexity of fibPow?
5. Look up the definition of pseudo-polynomial time.
(a) Write down the definition.
(b) Is fib a pseudo-polynomial time algorithm? Explain.
(c) Is fibIt a pseudo-polynomial time algorithm? Explain.
(d) Is fibPow a pseudo-polynomial time algorithm? Explain.
6. Solve the following recurrences exactly using the iteration method. In all cases, T (0) = 0. Answers should be
expressed in terms of T (n).
(a) T (n+ 1) = T (n) + 5
(b) T (n+ 1) = n+ T (n)
7. Solve the following recurrences exactly using the iteration method. In all cases, T (0) = 1. Answers should be
expressed in terms of T (n).
(a) T (n+ 1) = 2T (n)
(b) T (n+ 1) = 2n+1 + T (n)
8. Solve the following recurrences exactly using the iteration method. In all cases, T (1) = 1. Answers should be
expressed in terms of T (n).
(a) T (n) = n+ T (n/2) (Assume n has the form n = 2m.)
(b) T (n) = 1 + T (n/3) (Assume n has the form n = 3m.)
2
学霸联盟