$29
VE477 Homework 2
Questions preceded by a * are optional. Although they can be skipped without any deduction, it is important to know and understand the results they contain.
Ex. 1 — Basic complexity
1. Prove that
a) n3 − 3n2 − n + 1 = Θ(n3); * c) ∀a ∈ R, b ∈ R+, (n + a)b = Θ(nb );
b) n2 = O(2n);
2. For each pair of functions state whether f (n) = O(g (n), f (n)Ω(g (n)), f (n) = Θ(g (n)), or none.
a) f (n) = n√
, g (n) = n2 − 1;
* b) f (n) = 2n − n2, g (n) = n4 + n2;
n
3.
Find two functions f (n) and g (n) such that
a) f (n) = Θ(g (n)) and f (n) ̸= O(g (n))
b) f (n) = Ω(g (n)) and f (n) ̸= O(g (n))
4.
Order the following functions into increasing asymptotic order.
a) f (n) =
n
√
i
c) f3(n) = n
log n
1
i =1
f (n) = √n log n
n
2 + 4n + 6
d) f4(n) = 24√
3
b) 2
∑
Ex. 2 — Master Theorem
The goal of this exercise is to prove the Master Theorem (2.??) in the case where n is a power of b > 1. Both n and b, as well as all the other notations are similar to the ones used in the lecture slides. The only slight difference is that n is to be explicitly taken as an exact power of b.
1. We want to transform the evaluation of the master recurrence into a summation.
a) Draw the recursion tree corresponding to the master recurrence.
b) Determine
i – The depth of the tree;
ii – The number of leaves;
iii – The total cost for the all the nodes at each depth;
iv – Conclude that
logb n−1
T (n) = Θ(nlogb a) +
∑j
(2.1)
aj f (n/bj ).
=0
2. To obtain an asymptotic bound on sum (2.1), we focus on its right part and denote it
logb n−1
g (n) =
∑j
aj f (n/bj ).
=0
a) Assume f (n) = Θ(nlogb a)
i –
Prove that
logb n−1
n
logb a
∑
g (n) = Θ
j =0
aj
(bj )
.
* ii –
Show that
aj (
)
logb n−1
n
logb a
∑
= nlogb a logb n.
bj
▪ =0
iii – Conclude that g (n) = Θ(nlogb a log n).
b) Assume f (n) = O(nlogb a−ε), ε > 0.
* i –
Prove that
logb n−1
n
logb a−ε
∑
g (n) =
O
j =0
aj
(bj )
.
ii –
Show that
logb n−1
n
logb a−ε
nε
1
∑ aj
(
)
=
−
nlogb a−ε.
bj
bε
− 1
▪ =0
iii – Conclude that g (n) = O(nlogb a).
c) Assume af (n/b) ≤ cf (n), for some c < 1 and n large enough, and f (n) = Ω(nlogb a+ε), with
• > 0.
i – Observe that g (n) = Ω(f (n)).
ii – Prove that after j iterations aj f (n/bj ) ≤ cj f (n). * iii – Show that g (n) = O(f (n)).
iv – Conclude that g (n) = Θ(f (n)).
3. Using the results from questions 1 and 2, derive the Master Theorem as phrased in the lecture slides, in the case where n is an exact power of b.
Ex. 3 — Ramanujam numbers
A Ramanujam number is a positive integer n which can be written from two different ways as the sum of two cubes, i.e. there exists four positive integers a, b, c, and d less than n, such that n = a3 + b3 = c3 + d 3. Given n write some pseudocode to determine all the Ramanujam numbers smaller or equal to n. What is the complexity of the algorithm?
Ex. 4 — Critical thinking
Six pirates, ordered with respect to their seniority, want to share 300 pieces of gold among themselves.
They decide to proceed as follows:
1. The senior-most pirate proposes a way to distribute the coins;
2. All the pirates vote;
3. If at least half of them agree, the division remains;
4. Otherwise he is thrown overboard and the process is repeated with the senior-most remaining pirate;
Assuming all the pirates have proper thinking abilities and desire first to remain alive and second to become rich, how many pirates can remain alive and in that case how is the distribution handled?
