next up previous
Next: About this document ...

CS130N Problem set 2: Asymptotic orders of growth

1.
Let f(n) and g(n) be asymptotically non-negative functions. Show that $max(f(n),g(n)) = \Theta(f(n) + g(n))$.

2.
Show that for any real constants a and b, b > 0,

\begin{displaymath}
(n+a)^b = \Theta(n^b)
 \end{displaymath}

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)
$2n^2 + 3n + 1 = 2n^2 + \Theta(n)$
(b)
$T(n) = 2T(n/2) + \Theta(n)$ (why is it acceptable not to write the base case for this recurrence?)
(c)
$\sum_{i=1}^n O(i)$
(d)
$2n^2 + \Theta(n) = \Theta(n^2)$
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 $T(n) \leq cn$. We obviously have the base case. Now,

\begin{displaymath}
\begin{array}
{llll}
 T(n) & \leq & 2(cn/2) + n & \mbox{by I.H.} \\  & = & cn + n \\  & = & O(n)
 \end{array} \end{displaymath}

6.
Is 2n+1 = O(2n)? Is 22n = O(2n)?

7.
Show that $O(2^{\log_a(n)})$ is not the same as $O(2^{\log_b(n)})$,unless a = b of course.

8.
Show that $\log (n!) = \Theta(n\log n)$.

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)
$f(n) = \log n$
(e)
$f(n) = n\log n$

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 $\Theta(3^n)$.

11.
Use the fact that $\displaystyle \frac{d}{dx} \log\log x = \frac{1}{x\log x}$to show that

\begin{displaymath}
\sum_{k=2}^n \frac{1}{k\log k} = O\left( \log\log n\right).\end{displaymath}

12.
Prove or disprove:
(a)
$f(n) = \Theta(g(n))$ and $g(n)=\Theta(h(n))$ implies $f(n)=\Theta(h(n))$.
(b)
f(n) = O(g(n)) and g(n)=O(h(n)) implies f(n)=O(h(n)).
(c)
$f(n) = \Omega(g(n))$ and $g(n)=\Omega(h(n))$ implies $f(n)=\Omega(h(n))$.
(d)
f(n) = O(g(n)) implies g(n) = O(f(n)).
(e)
f(n) = O(g(n)) iff $g(n) = \Omega(f(n))$.
(f)
f(n) = O(g(n)) implies $g(n) = \Omega(f(n))$.
(g)
f(n) = O(g(n)) implies 2f(n)=O(2g(n)).
(h)
$f(n) = \Theta(g(n))$ iff $g(n) = \Theta(f(n))$

13.
Let $a \geq 1$ 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 $\lfloor n/b \rfloor$ or $\lceil n/b \rceil$. Show that T(n) can be bounded asymptotically as follows:
(a)
If $f(n) = O(n^{log_b{a - \epsilon}})$ for some $\epsilon \gt 0$,then $T(n) = \Theta(n^{log_b{a}})$.
(b)
If $f(n) = \Theta(n^{log_b{a}})$, then $T(n) = \Theta(n^{log_b{a}}\lg{n})$
(c)
If $f(n) = \Omega(n^{log_b{a + \epsilon}})$ for some $\epsilon \gt 0$, and if $af(n/b) \leq cf(n)$ for some c < 1 and all sufficiently large n, the $T(n) = \Theta(f(n))$.
[Note: The above is called the master theorem. The tutors may discuss some applications.]


 
next up previous
Next: About this document ...
Subhashis Banerjee
1/22/2001