1
$\begingroup$

Are statements below true or false?

$(1+1/n)^n = \Theta(\log n)$

$\log \log n = o(\log n)$ Note that it is little-o, not big-O

For first statement, I thought it would have $\Theta(n^2)$ complexity so it is false, while the second statement is true. Is my assumption correct?

  • 2
    **1.** For the first, what do you know about the limit of that expression as $n \to \infty$? (Hint: there's a very good chance that you've seen that limit if you've studied calculus!) **2.** You should be able to *show* it; you should think of the word "assumption" as a dirty word, for a simple comparisons such as this. Given that you're supposed to determine whether log log *n* ∈ o(log *n*), as opposed to *e.g.* Θ(log *n*), you can test the correctness using a ratio test of some sort. Can you see how?2011-08-28
  • 0
    I studied Cal like few years ago such that I do not remember most of the common limit problems.. This is so sad :P2011-08-28
  • 1
    Suppose that you found out that the expression converged to a mathematical constant of some sort, such as π or 271/100. What would that mean for the answer?2011-08-28
  • 2
    If you don't remember calculus, then perhaps this course is not for you... At least discuss your predicament with the instructor.2011-08-28
  • 0
    If you need to brush up, then it should be enough to review things about: **1. computing limits** (for which the power-tool of l'Hôptial's rule will be particularly useful); **2. simple integrals** (*e.g.* integrating polynomials, logarithms; especially integration by parts) and **3. infinite series** (mostly summations of polynomials *f(j)*, for *j* ranging from 1 to *n*). Connections between integrals and infinite sums are also important (not Riemann sums, just simple ways you can bound one by the other). If you can catch yourself up on these topics, you should be able to handle it.2011-08-28
  • 0
    @Niel de Beaudrap Thanks! I will study over those topics. In fact, some of my memories are coming back.2011-08-28

1 Answers 1

2

It is a standard exercise to show that $a_n := \left( 1+\frac1n \right)^n$ is bounded between $2$ and $3$ for all $n$. (In fact, this sequences approaches $e = 2.718\cdots$.) So $a_n = \Theta(1)$ by definition of $\Theta$. Since $\Theta$ is an equivalence relation and $1 \notin \Theta(\log n)$, it follows that $a_n \notin \Theta(\log n)$ as well.

The second statement $\log \log n = o(\log n)$ is true. There are many ways to show this; for instance: $$\log n = \exp(\log \log n) = \exp\left(\frac{1}{2} \log \log n \right)^2 \geq \left( \frac{1}{2} \log \log n \right)^2 = \frac{1}{4} (\log \log n)^2 ,$$ and $\log \log n \to \infty$ as $n \to \infty$. (I used the fact that $e^x > x$ for all $x$ in the above.)

  • 0
    If anyone needs a reference to the bounds on $a_n$, a proof of this fact can be found in Analysis I by Amann and Escher on p 165.2011-11-01