Let f(n) and g(n) be asymptotically non-negative functions.
Show that .
2.
Show that for any real constants a and b, b > 0,
3.
Explain why the statement, "The running time of insertion sort
is at least O(n2)," is content-free.
4.
What do we mean in each of the following?
(a)
(b)
(why is it acceptable
not to write the base case for this recurrence?)
(c)
(d)
5.
Consider the recurrence T(1) = 1, T(n) = 2T(n/2) + n. What
is wrong in the following proof by induction that T(n) = O(n)?
We prove . We obviously have the base case. Now,
6.
Is 2n+1 = O(2n)? Is 22n = O(2n)?
7.
Show that is not the same as ,unless a = b of course.
8.
Show that .
9.
For which of the following functions is it true that f(2n) = O(f(n))?
(a)
f(n) = n
(b)
f(n) = n4
(c)
f(n) = 2n
(d)
(e)
10.
In a certain population of amoebae, there are ``active'' amoebae and
``passive'' amoebae. Every minute, each active amoebae is turned into
3 active amoebae and 7 new passive ones. All the old passive amoebae
remain unchanged. Starting with a single active amoeba, how many
amoebae will there be after n minutes? Show that this is .
11.
Use the fact that
to show that
12.
Prove or disprove:
(a)
and implies .
(b)
f(n) = O(g(n)) and g(n)=O(h(n)) implies f(n)=O(h(n)).
(c)
and implies .
(d)
f(n) = O(g(n)) implies g(n) = O(f(n)).
(e)
f(n) = O(g(n)) iff .
(f)
f(n) = O(g(n)) implies .
(g)
f(n) = O(g(n)) implies 2f(n)=O(2g(n)).
(h)
iff
13.
Let and b > 1 be constants, let f(n) be
a function, and let T(n) be defined on nonnegative integers by the recurrence
T(n) = aT(n/b) + f(n)
where we interpret n/b to mean either or
. Show that T(n) can be bounded
asymptotically as follows:
(a)
If for some ,then .
(b)
If , then
(c)
If for some , and if for some c < 1 and all sufficiently
large n, the .
[Note: The above is called the master theorem. The tutors may
discuss some applications.]