Description
1. Solve this sum of a geometric series: P∞
i=1
(2/5)i
.
2. (a) How many binary digits are there in 250 and 1050? How are the two numbers related?
Hint: This is a question about logarithm.
(b) Show that loga
(x) = c ∗ logb
(x) for some constant c expressed only in terms of constants
a and b.
3. (a) Problem 5.19 of the textbook. Except in the obvious cases, give reasons for your ranking.
(b) Rank the following functions: log n, log(n
2
), log log n, and log2 n. Explain reasons for
your ranking.
You may find it useful to remember that one way to compare the relative growth rates of
f(n) and g(n) is to look at the ratio f(n)/g(n) as n → ∞. If that ratio approaches 0, then
g grows faster than f: f(n) = O(g(n)). If it approaches infinity then f grows faster than g:
f(n) = Ω(g(n)). If the ratio approaches a constant different from both 0 and ∞, then f and
g grow at the same rate.
4. Problem 5.26 of the textbook.
5. Use the telescoping technique to derive this equation:
Xn
i=1
i
2 =
n(n + 1)(2n + 1)
6
