# CS130N Problem set 2: Asymptotic orders of growth

1.
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.]