ECS 122A – Algorithm & Analysis Homework 02 Solution
Problem 1 (5 points each)
For each of the recursive function, write down its runtime as a recurrence. Note: If you write 1 or any constant number instead of Θ(1), that’s ok.
Answer: T(n) = T(n − 1) + Θ(1) 2. fun2:
Copyright By PowCoder代写 加微信 powcoder
Answer: T(n) = T(n−1)+T(n−2)+Θ(1) 3. fun3:
1 2 3 4 5 6 7 8
Answer: T(n) = 2T( n2 ) + Θ(1) 4. fun4:
1 2 3 4 5 6
if n <= 0:
return fun1(n-1) * n
if n <= 1:
return fun2(n-1) + fun2(n-2)
fun3(A[0...n-1]): if n <= 0:
return 1 if n == 0:
return A[1]
a = fun3(A[0...n/2])
b = fun3(A[n/2+1...n-1]) return a + b
fun4(A[0...n-1]): if n <= 0:
return 1 if n == 0:
return A[1]
return fun4(A[0...n/3]) + fun4(A[n/3+1...2n/3]) + fun4(A[2n/3+1...n-1])
Answer: T(n) = 3T( n3 ) + Θ(1)
Problem 2 (16 points each)
Prove or disapprove the time complexity guess for each of the following recurrences using the subsitu- tion method.
Note: You only need to get a condition for c. You don’t have to pick an actual number for it.
1. T(n)=T(n−1)+nisO(n2) Answer:
Letk≥1.AssumeT(n)≤cn2 forsomeconstantc>0andforall1≤n
Pick c = 1, then k ≥ 1. Conclusion: T(n) is O(n2).
To show T(k) ≤ clogk, i.e.,
T ( k ) = T ( 2k ) + 1 ≤ c l o g 2k + 1
= clogk − clog2 + 1 = clogk − c + 1
clogk−c+1 ≤ clogk c≥1
Pick c = 1. So there exists c > 0 such that T(k) ≤ clogk. Conclusion: T(n) is O(logn)
3. T(n) = T(n/2) + n2 is O(nlogn) Answer:
There are three ways to disprove it. If asked in the exam, the second way of proving a lower-order term as lower bound should be used.
(a) Intuitively, T(n) has n2 in it. It must be at least O(n2).
(b) By proving T(n) is Ω(n2): Letk≥1.Assumeforall1≤n
To show T(k) ≥ ck2, i.e.,
T ( k ) = T ( 2k ) + k 2 ≥ c ( 2k ) 2 + k 2
c ( 2k ) 2 + k 2 ≥ c k 2 c ( 12 ) 2 + 1 ≥ c 1 ≥ 34 c
c ≤ 43 Pick c = 1. So there exists c > 0 such that T(k) ≥ ck2.
Conclusion: T(n) is Ω(n2). It cannot be O(nlogn).
(c) Try to prove that T(n) is O(nlogn) using substitution:
Let k ≥ 1. Assume T(n) ≤ cnlogn for some constant c > 0 and for all 1 ≤ n < k.
To show T(k) ≤ cklogk, i.e,.
T ( k ) = T ( 2k ) + k 2
≤ c ( 2k ) l o g 2k + k 2
= cklogk− ck +k2 22
cklogk − ck + k2 ≤ cklogk 22
− 2c + k ≤ 2c l o g k 2k ≤ clogk + c
When k ≥ 1, k > logk. So no matter what c is, 2k will be larger than clogk + c for sufficiently large k.
If we try to add a lower order term such as dn: Assume T(n) ≤ cnlogn + dn for some constant c > 0 and for all 1 ≤ n < k.
T ( k ) = T ( 2k ) + k 2
≤ c ( 2k ) l o g 2k + d ( 2k ) + k 2
= cklogk− ck + dk +k2 222
To show T(k) ≤ cklogk + dk, i.e.,
cklogk− ck + dk +k2 ≤ cklogk+dk
− 2c + k ≤ 2c l o g k + 2d
2k ≤ clogk + d + c
When k ≥ 1, k > logk. So no matter what c and d are, 2k will be larger than clogk + d + c for sufficiently large k.
Conclusion: T(n) is not O(nlogn).
4. T(n) = 3T(n2 ) + n is O(nlog3) Answer:
Letk≥1.AssumeT(n)≤cnlog3 forsomeconstantc>0andforall1≤n
Conclusion: T(n) is O(nlog3).
5. T(n)=T(n−1)+T(n2)+nisO(n2n) Answer:
Letk≥1.AssumeT(n)≤cn2n forsomeconstantc>0andforall1≤n
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com