Integers

By definition,
(a) show that 1k + 2k + · · · + n
k
is O(n
k+1), where k is a positive integer.
(b) show that (n
3 + 2n)/(2n + 1) is O(n
2
).
(c) Prove that (n + 3)3 = Θ(n
3
)
2. (a) Is 2n+1 = O(2n
)? why?
(b) Is 22n = O(2n
)? why?
3. Order the following functions into a list such that if f(n) comes before g(n) in the list then
f(n) = O(g(n)). If any two (or more) of the same asymptotic order, indicate which.
(a) Start with these basic functions
n, 2
n
, n lg n, n3
, lg n, n − n
3 + 7n
5
, n2 + lg n
(b) Combine the following functions into your answer for part (a). Assume that 0 <  < 1.
e
n
,
√
n, 2
n−1
, lg lg n, (
√
2)lg n
, ln n, (lg n)
2
, n!, n1+
, 1
4. Recall that we have discussed the method of explicit substitution to solve a recurrence relation.
It expands out the recurrence a few times until a pattern emerges. For instance, let us start with
the recurrence
T(n) = 2T(n/2) + cn.
where c is a positive constant. By repeatedly applying this rule, we can bound T(n) in terms of
T(n/2), then T(n/2
2
), then T(n/2
3
), and so on, at each step getting closer to the basis value of
T(1) = O(1):
T(n) = 2T(n/2) + cn = 2[2T(n/2
2
) + cn/2] + cn = 22T(n/2
2
) + 2cn
= 22
[2T(n/2
3
) + cn/2
2
] + 2cn = 23T(n/2
3
) + 3cn = . . .
A pattern is emerging. The general term is T(n) = 2kT(n/2
k
) + kcn. Plugging in k = lg n, we
get T(n) = n · T(1) + c n lg n = Θ(n lg n).
Do the same thing for the following recurrence
T(n) = 3 · T(
n
2
) + cn.
(a) What is the general kth term in this case?
(b) What value of k should be plugged in to get the answer?
5. Find the solution of the in each of the following recurrences, and then give tight bounds for T(n).
(a) T(n) = T(n − 1) + 1/n with T(0) = 0.
(b) T(n) = T(n − 1) + c
n with T(0) = 1, where c > 1 is some constant
(c) T(n) = 2 T(n − 1) + 1