Sample Solutions

Sample Solutions
Assigment 2
CSCI 3110 — Summer 2014
Question 1
The correct order is
(lg n)2
p
n
4lg n (= n2 )
n lg n
n
Let’s prove it:
p
• (lg n)2 ∈ o( n):
First we observe that
(lg n)2
lim p
=0
n→∞
n
⇐⇒
lim
n→∞
lg n
n1/4
Now we have
lim
lg n
n→∞
n1/4
lg e/n
= lim
n→∞
= lim
n→∞
(1/4)n−3/4
4 lg e
n1/4
= 0.
•
p
n ∈ o(n):
p
lim
n→∞
1
= lim p
n→∞
n
n
= 0.
n
• n ∈ o(n lg n):
lim
n→∞
n
n lg n
= lim
n→∞
= 0.
• n lg n ∈ o(n 2 ):
1
1
lg n
= 0.
2n .
n lg n
lim
n→∞
n2
= lim
n→∞
= lim
n→∞
= lim
n→∞
lg n
n
lg e/n
1
lg e
n
= 0.
• n 2 = 4lg n = 22 lg n ∈ o(2n ):
Here we use the rule that f (n) ∈ o(g(n)) implies a f (n) ∈ o(a g(n) ). We use a = 2. Then f (n) = 2 lg n
and g(n) = n. Using the calculation from the previous point, we have
lim
2 lg n
n
n→∞
= 2 lim
n→∞
lg n
n
= 2 · 0 = 0.
Question 2
a. f (n) = 2n 2 + 3n 3 − 143n lg n + 12 ∈ Θ(n 3 ):
First we determine constants n1 and c1 such that, for all n ≥ n1 , we have c1 n3 ≤ f (n):
f (n) =
2n2 + 3n3 − 143n lg n + 12
0 ≥ −2n2
− 12
3n3 − 143n lg n
f (n) ≥
∀n
3
∀ n ≥ 72
n3
∀ n ≥ 72
− 2n + 143n lg n
0≥
f (n) ≥
∀n
So we have n1 = 72 and c1 = 1. Now we determine constants n2 and c2 such that, for all n ≥ n2 ,
we have f (n) ≤ c2 n3 :
f (n) =
2n2 + 3n3 − 143n lg n + 12
0≤
f (n) ≤
∀n ≥ 1
143n lg n
2n2 + 3n3
2
0 ≤ −2n + 2n
+ 12
3
∀n ≥ 1
∀n ≥ 1
f (n) ≤
5n3
+ 12
∀n ≥ 1
0≤
3
− 12
∀n ≥ 1
f (n) ≤
12n
17n3
∀n ≥ 1
So we have n2 = 1 and c2 = 17. Now we choose n0 = max(n1 , n2 ) = 72, and we have n3 ≤
f (n) ≤ 17n3 , for all n ≥ 72.
2
b. f (n) = n lg n + n 2 − 11n − 18 ∈ Θ(n 2 ):
Same procedure as in the previous question: First we look for constants n1 and c1 such that, for
all n ≥ n1 , we have c1 n3 ≤ f (n):
f (n) =
n lg n + n2 − 11n − 18
0 ≥ −n lg n
∀n ≥ 1
n2 − 11n − 18
f (n) ≥
0≥
f (n) ≥
0≥
f (n) ≥
1
− n2 + 11n
2
1
∀n ≥ 1
∀ n ≥ 22
n2
− 18
∀ n ≥ 22
− n2
4
+ 18
∀n ≥ 9
2
1
1
4
n2
∀ n ≥ 22
So we have n1 = 22 and c1 = 1/4. Now the upper bound:
f (n) =
n lg n + n2 − 11n − 18
0≤
11n + 18
f (n) ≤
n lg n + n2
∀n ≥ 0
2
∀n ≥ 1
2n2
∀n ≥ 1
0 ≤ −n lg n + n
f (n) ≤
∀n ≥ 0
So f (n) ≤ 2n2 for all n, and we have n2 /4 ≤ f (n) ≤ 2n2 for all n ≥ 22.
3
p
c. f (n) = n lg n − 6n + 153 n − 1011 ∈ Θ(n lg n):
Lower bound:
f (n) =
0≥
f (n) ≥
p
n lg n − 6n + 153 n − 1011
p
− 153 n
∀n ≥ 0
n lg n − 6n
∀n ≥ 0
− 1011
1
0 ≥ − n lg n + 6n
2
1
∀ n ≥ 212
n lg n
− 1011
∀ n ≥ 212
0 ≥ − n lg n
4
+ 1011
∀ n ≥ 500
f (n) ≥
f (n) ≥
2
1
1
4
∀ n ≥ 212
n lg n
So we have n1 = 212 and c1 = 1/4. Upper bound:
p
f (n) = n lg n − 6n + 153 n − 1011
0≤
f (n) ≤ n lg n
0 ≤ n lg n
+ 1011
6n
p
+ 153 n
p
− 153 n
f (n) ≤ 2n lg n
∀n ≥ 0
∀n ≥ 0
∀ n ≥ (153)2 = 23409
∀ n ≥ 23409
So we have n2 = 23409 and c2 = 2. Taking n0 = max(n1 , n2 ) = 212 , we obtain that
f (n) ≤ 2n lg n, for all n ≥ 212 .
4
1
n lg n
4
≤

Download Report