next up previous
Next: About this document ...

CS130N Problem set 2: Asymptotic orders of growth

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

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

(n+a)^b = \Theta(n^b)

Explain why the statement, "The running time of insertion sort is at least O(n2)," is content-free.
What do we mean in each of the following?
$2n^2 + 3n + 1 = 2n^2 + \Theta(n)$
$T(n) = 2T(n/2) + \Theta(n)$ (why is it acceptable not to write the base case for this recurrence?)
$\sum_{i=1}^n O(i)$
$2n^2 + \Theta(n) = \Theta(n^2)$
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,

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

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

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

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

For which of the following functions is it true that f(2n) = O(f(n))?
f(n) = n
f(n) = n4
f(n) = 2n
$f(n) = \log n$
$f(n) = n\log n$

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)$.

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

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

Prove or disprove:
$f(n) = \Theta(g(n))$ and $g(n)=\Theta(h(n))$ implies $f(n)=\Theta(h(n))$.
f(n) = O(g(n)) and g(n)=O(h(n)) implies f(n)=O(h(n)).
$f(n) = \Omega(g(n))$ and $g(n)=\Omega(h(n))$ implies $f(n)=\Omega(h(n))$.
f(n) = O(g(n)) implies g(n) = O(f(n)).
f(n) = O(g(n)) iff $g(n) = \Omega(f(n))$.
f(n) = O(g(n)) implies $g(n) = \Omega(f(n))$.
f(n) = O(g(n)) implies 2f(n)=O(2g(n)).
$f(n) = \Theta(g(n))$ iff $g(n) = \Theta(f(n))$

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:
If $f(n) = O(n^{log_b{a - \epsilon}})$ for some $\epsilon \gt 0$,then $T(n) = \Theta(n^{log_b{a}})$.
If $f(n) = \Theta(n^{log_b{a}})$, then $T(n) = \Theta(n^{log_b{a}}\lg{n})$
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