- 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*(*n*)," is content-free.^{2} - 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*) = 2*T*(*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 2
^{n+1}=*O*(2^{n})? Is 2^{2n}=*O*(2^{n})? - 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*(2*n*) =*O*(*f*(*n*))?- (a)
*f*(*n*) =*n*- (b)
*f*(*n*) =*n*^{4}- (c)
*f*(*n*) = 2^{n}- (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 2^{f(n)}=*O*(2^{g(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*)*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 .

**master theorem**. The tutors may discuss some applications.]