ECS 122A – Algorithm & Analysis Homework 03 Solution
Question 1 (10 points each)
For the following recurrences, use recursion tree to find the tightest possible Big-O. (Hint: Check the Big-O guesses for the recurrences in Homeowrk 2.)
1. T(n) = T(n−1)+n Answer:
Copyright By PowCoder代写 加微信 powcoder
T(n) is O(n2)
T(n) = n+(n−1)+(n−2)+…+1 = n(n+1)
2. T(n)=T(n/2)+1 Answer:
T(n) is O(logn).
3. T(n) = T(n/2) + n2 Answer:
T(n) = 1×logn = logn
T(n) = n2 +(n2)2 +(n4)2 +(n8)2 +…+1 =n2(1+1+ 1 + 1 +…+1)
4 16 64 logn 1
= n2 ∑ 4i i=0
= n 2 1 − ( 14 ) l o g n + 1 1 − 14
=4n2(1− 1 ) 3 4n2
T(n) is O(n2).
4. T(n)=3T(n2)+n
T(n) = n+ 23n+ 49n+…+1
logn 3 i = n ∑(2)
= n 1 − ( 32 ) l o g n + 1
= 2 n ( ( 32 ) l o g n + 1 − 1 )
= 3logn+1 − 2n = 3 · 3logn − 2n
= 3 · nlog3 − 2n
T(n) is O(nlog3).
5. T(n) = T(n−1)+T(n2)+n Answer:
T(n) = (n + 32n + 94n + … + 1) − (some number, can be ignored) ∑n 3 i
= n ( 2 ) (Note: the length of the longest branch is) n i=1
= n 1 − ( 32 ) n + 1 1 − 32
= 3 n ( 32 ) n − 2 n T(n) is O(n(23)n).
Question 2 (10 points each)
For the following recurrences, use the master method to find the Big-Θ if possible. If not, explain why. Assume that T(n) is constant for sufficiently small n.
1. T(n) = 2T(n/4) + 1 Answer:
f (n) = 1 nlogba = nlog42 = n21
f (n) is smaller. Try Case 1.
Letε= 14.Then1isO(n12−14)=O(n14).(Any0<ε≤ 12 works.) So Case 1 applies. T(n) is Θ(n21 ).
2. T(n) = 2T(n/4) + Answer:
Case 2 applies. T(n) is Θ(n21 logn).
3. T(n) = 2T(n/4) + n Answer:
1 f(n) = n2
n l o g b a = n 12
f (n) = n 4
n l o g b a = n 12
• Letε= 14.ThennisΩ(n12+14)=Ω(n34).(Any0<ε≤ 21 works.)
f (n) is larger. Try Case 3. • Regularity condition:
Let c = 21 :
af(nb) = 2f(n4) = n2 c f ( n ) = n2
(Any 12 ≤ c < 1 works.) The regularity condition holds. So Case 3 applies. T(n) is Θ(n).
4. T(n) = 2T(n/4) + n2 Answer:
f(n) = n2 n l o g b a = n 12
f (n) is larger. Try Case 3.
• Letε= 14.Thenn2 isΩ(n12+14)=Ω(n43).(Any0<ε≤ 23 works.)
• Regularity condition:
Let c = 81 :
(Any 18 ≤ c < 1 works.)
So Case 3 applies. T(n) is Θ(n2).
5. T(n) = 4T(n/3) + nlogn Answer:
af(n) = 2f(n) = 2×(n)2 = n2 b448
c f (n) = n2 8
f (n) = nlogn nlogba = nlog34
f (n) is smaller. Try Case 1.
log34 ≈ 1.26, Let ε = (log34) − 1.1 ≈ 0.16.
Then nlogba−ε = n1.1. f(n) = nlogn is O(n1.1). So Case 1 applies. T(n) is Θ(nlog34).
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com