Week 5 – Extra Exercises
EXERCISE 1. Prove each of the following, using the defnition of
O().
(a) Show that 7n + 12 ∈ O(n)
(b) Show that 8n4 + n + 5 ∈ O(n4).
(c) Show that n2 – 5n ∈/ O(n)
(d) Show that 3n3 – n2 ∈/ O(n2).
1 / 28
Week 5 – Extra Exercises
EXERCISE 1. Prove each of the following, using the defnition of
O().
(a) Show that 7n + 12 ∈ O(n)
Solution
Let M = 19 and n0 = 1. We will show that for all n > 1,
7n + 12 < 19n.
Let n > 1 be arbitrary. Then
7n + 12 < 7n + 12n = 19n,
as needed.
2 / 28
Week 5 – Extra Exercises
(b) Show that 8n4 + n + 5 ∈ O(n4).
Solution
Let M = 14 and n0 = 1. We claim that for all n > 1,
8n4 + n + 5 < 14n4.
Let n > 1 be arbitrary. Then n4 > n > 1, and so
8n4 + n + 5 < 8n4 + n4 + 5n4 = 14n4,
as needed.
3 / 28
Week 5 – Extra Exercises
(c) Show that n2 – 5n ∈/ O(n)
Solution
Let M > 0 and n0 > 0 be arbitrary. We will fnd n > n0 such
that n2 – 5n > Mn.
Let n = max {n0 + 1, 11, 2M}. Then n > n0, and n > 2M,
which implies that 12n > M. Finally, n > 10, which implies
that 1
n
< 1
10.
Now,
n2 – 5n = n2 1 – n5 > n2 1 – 10 5  = 1 2n2 > Mn,
as needed.
4 / 28
Week 5 – Extra Exercises
(d) Show that 3n3 – n2 ∈/ O(n2).
Solution
Let M > 0 and n0 > 0 be arbitrary. We will fnd n > n0 so
that 3n3 – n2 > n2.
Let n = max {n0 + 1, M + 1}. Then n > n0 and n > M. Also,
n > 1, which implies that n3 > n2. We have
3n3 – n2 = n3 3 – n1 > n3 (3 – 1) = 2n3 > n3 > Mn2,
as needed.
5 / 28
Week 5 – Extra Exercises
EXERCISE 2. Prove each of the following using the defnition of
O().
(a) Show that 4n ∈ O(n!)
(b) Show that 4n + 2n ∈ O(n!)
(c) Show that n! ∈ O(nn)
(d) Show that 3n ∈/ O(2n)
6 / 28
Week 5 – Extra Exercises
EXERCISE 2. Prove each of the following using the defnition of
O().
(a) Show that 4n ∈ O(n!)
Solution
Let M = 43 and n0 = 3. We will show that for all n > 3,
4n < 43n!.
Let n > 3 be arbitrary. Then n! is a product of at least 4
factors:
n! = n · (n – 1) · . . . · 4
| {z }
n–3 terms
·3 · 2 · 1
Notice that each of the factors indicated above is greater than
or equal to 4.
7 / 28
Week 5 – Extra Exercises
Using this observation, we have
43n! = 43 n · (n – 1) · . . . · 4
| {z }
n–3 terms
·3 · 2 · 1
≥ 43 4 · 4 · . . . · 4
| {z }
n–3 terms
·3 · 2 · 1
≥ 43 4 · 4 · . . . · 4
| {z }
n–3 terms
= 43 · 4n–3 = 4n,
as needed.
8 / 28
Week 5 – Extra Exercises
(b) Show that 4n + 2n ∈ O(n!)
Solution
Let M = 2 · 43 and n0 = 3. We will show that for all n > 3,
4n + 2n < 2 · 43n!.
Let n > 3 be arbitrary. Observe that
4n + 2n < 4n + 4n = 2 · 4n. Also observe that n! is a product
of at least 4 factors:
n! = n · (n – 1) · . . . · 4
| {z }
n–3 terms
·3 · 2 · 1
Notice that each of the factors indicated above is greater than
or equal to 4.
9 / 28
Week 5 – Extra Exercises
Now we see that
2 · 43n! = 2 · 43 n · (n – 1) · . . . · 4
| {z }
n–3 terms
·3 · 2 · 1
≥ 2 · 43 4 · 4 · . . . · 4
| {z }
n–3 terms
·3 · 2 · 1
≥ 2 · 43 · 4n–3 = 2 · 4n
≥ 4n + 2n,
as needed.
10 / 28
Week 5 – Extra Exercises
(c) Show that n! ∈ O(nn)
Solution
Let M = 1 and n0 = 1. We claim that for all n > 1, n! ≤ nn.
Let n > 1 be arbitrary. Then
n! = n · (n – 1) · . . . · 2 · 1
| {z }
n factors
≤ n · n · . . . · n · n
| {z }
n factors
= nn,
as needed.
11 / 28
Week 5 – Extra Exercises
(d) Show that 3n ∈/ O(2n)
Solution
Let M > 0 and n0 > 0 be arbitrary. We will fnd n > n0 so
that 3n > M2n.
Let n = max nn0 + 1, log3/2(M) + 1o. Then n > n0. Further,
n > log3/2(M),
which implies that
32n > M
and thus
3n > M2n,
as needed.
12 / 28
Week 5 – Extra Exercises
EXERCISE 3. Prove each of the following using the defnition of
Ω().
(a) Show that n5 ∈ Ω(√n)
(b) Show that n3 – n ∈ Ω(n2)
(c) Show that 2n2 + n + 1 ∈/ Ω(n3)
(d) Show that 2n ∈/ Ω(n2n)
13 / 28
Week 5 – Extra Exercises
EXERCISE 3. Prove each of the following using the defnition of
Ω().
(a) Show that n5 ∈ Ω(√n)
Solution
Let M = 1 and n0 = 25. We will show that for all n > 25,
n5
> √n.
Let n > 25 be arbitrary. Then √n > 5, and therefore
n 5
=
1 5
√n√n > 1
5
(5)√n = √n,
as needed.
14 / 28
Week 5 – Extra Exercises
(b) Show that n3 – n ∈ Ω(n2)
Solution
Let M = 1 and n0 = 2. We will show that for all n > 2,
n3 – n > n2.
Let n > 2 be arbitrary. Then n2 > 2, which implies that
12n
< 1
2. We fnd that
n3 – n = n3 1 – n12  > n3 1 – 1 2 = 1 2n3 > 12(2)n2 = n2,
as needed.
15 / 28
Week 5 – Extra Exercises
(c) Show that 2n2 + n + 1 ∈/ Ω(n3)
Solution
Let M > 0 and n0 > 0 be arbitrary. We need to fnd n > n0
so that 2n2 + n + 1 < Mn3.
Let n = max n0 + 1, M4 + 1 . Then n > n0 and n > 1, which
implies that n2 > n and n2 > 1. Also, n > M4 , which implies
that 4 < Mn.
Combining these observations yields
2n2 + n + 1 < 2n2 + n2 + n2 = 4n2 < (Mn)n2 = Mn3,
as needed.
16 / 28
Week 5 – Extra Exercises
(d) Show that 2n ∈/ Ω(n2n)
Solution
Let M > 0 and n0 > 0 be arbitrary. We will fnd n > n0 so
that 2n < Mn2n.
Let n = max n0 + 1, M1 + 1 . Then n > n0, and n > M1 ,
which implies that Mn > 1. We see that
2n = 1 · 2n < Mn2n,
as needed.
17 / 28
Week 5 – Extra Exercises
EXERCISE 4. Use the defnition of Θ() to prove each of the
following.
(a) Show that 3n2 + 5 ∈ Θ(n2)
(b) Show that n3 + n ∈ Θ(n3)
(c) Show that n4 – 5n2 ∈/ Θ(n3)
(d) Show that n log2(n) ∈/ Θ(n).
18 / 28
Week 5 – Extra Exercises
EXERCISE 4. Use the defnition of Θ() to prove each of the
following.
(a) Show that 3n2 + 5 ∈ Θ(n2)
Solution
Let M1 = 3, M2 = 8 and n0 = 1. We will show that for all
n > 1, 3n2 < 3n2 + 5 and 3n2 + 5 < 8n2.
Let n > 1 be arbitrary. Then n2 > 1.
First, it is immediate that 3n2 < 3n2 + 5.
Also,
3n2 + 5 < 3n2 + 5n2 = 8n2,
as needed.
19 / 28
Week 5 – Extra Exercises
(b) Show that n3 + n ∈ Θ(n3)
Solution
Let M1 = 1, M2 = 2 and n0 = 1. We will show that for all
n > 1, n3 < n3 + n and n3 + n < 2n3.
Let n > 1 be arbitrary. Then n2 > 1, and so n3 > n.
Since n > 0, it is immediate that n3 < n3 + n.
Furthermore,
n3 + n < n3 + n3 = 2n3,
as needed.
20 / 28
Week 5 – Extra Exercises
(c) Show that n4 – 5n2 ∈/ Θ(n3)
Solution
Let M1, M2, n0 > 0 be arbitrary. We will fnd n > n0 so that
n4 – 5n2 > M2n3.
Let n = max {n0 + 1, 2M2 + 1, 11}. Then n > n0, and
n > 2M2, which implies that n2 > M2. Also, n > 10, which
implies that n2 > 10.
Now,
n4 – 5n2 = n4 1 – n52  > n4 1 – 10 5  = 1 2n4 > M2n3,
as needed.
21 / 28
Week 5 – Extra Exercises
(d) Show that n log2(n) ∈/ Θ(n).
Solution
Let M1, M2, n0 > 0 be arbitrary. We will construct n > n0 so
that n log2(n) > M2n.
Let n = max n0 + 1, 2M2 + 1 . Then n > n0, and
n > 2M2,
which implies that
log2(n) > M2.
Multiplying this inequality by n yields
n log2(n) > M2n,
as needed.
22 / 28
Week 5 – Extra Exercises
EXERCISE 5. Use the defnitions of o() and ω() to prove the
following.
(a) Show that 3n ∈ o(n!)
(b) Show that n1/2 ∈ ω(n1/3)
(c) Show that n5 ∈/ o(n5 – 10n)
(d) Show that 6n + 5 ∈/ ω(n2)
23 / 28
Week 5 – Extra Exercises
EXERCISE 5. Use the defnitions of o() and ω() to prove the
following.
(a) Show that 3n ∈ o(n!)
Solution
Let M > 0 be arbitrary. We will fnd n0 > 0 so that for all
n > n0, 3n < Mn!.
Let n0 = max n23M3 , 3o, and let n > n0 be arbitrary. Then
n > 3, and n > 23M3 , which implies that 2Mn > 33.
Now, observe that
n! = n · (n – 1) · . . . · 3
| {z }
n–3 terms
·2 · 1,
where each of the n – 3 terms indicated above is ≥ 3. Since
n > 3, there is at least one such term.
24 / 28
Week 5 – Extra Exercises
Now we have
Mn! = M · n · (n – 1) · . . . · 3
| {z }
n–3 terms
·2 · 1
≥ M · n 3 · . . . · 3
| {z }
n–3 terms
·2 · 1
= 2Mn · 3n–3
> 33 · 3n–3 = 3n,
as needed.
25 / 28
Week 5 – Extra Exercises
(b) Show that n1/2 ∈ ω(n1/3)
Solution
Let M > 0 be arbitrary, and let n0 = M6. We claim that for
all n > n0, n1/2 > Mn1/3.
Let n > n0 be arbitrary. Then n > M6, which implies that
n1/6 > M. Consequently,
n1/2 = n1/6n1/3 > Mn1/3,
as needed.
26 / 28
Week 5 – Extra Exercises
(c) Show that n5 ∈/ o(n5 – 10n)
Solution
Let M = 1, and let n0 > 0 be arbitrary. We will fnd n > n0
so that n5 > n5 – 10n.
Let n = n0 + 1. Then n > n0, and it is immediate that
n5 > n5 – 10n.
27 / 28
Week 5 – Extra Exercises
(d) Show that 6n + 5 ∈/ ω(n2)
Solution
Let M = 11, and let n0 > 0 be arbitrary. We will fnd n > n0
so that 6n + 5 < 11n2.
Let n = n0 + 1. Then n > n0, and n > 1, which implies that
n2 > n > 1. We see that
6n + 5 < 5n2 + 5n2 = 11n2,
as needed.
28 / 28