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
    $\begingroup$ 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? $\endgroup$ – Niel de Beaudrap Aug 28 '11 at 21:34
  • $\begingroup$ I studied Cal like few years ago such that I do not remember most of the common limit problems.. This is so sad :P $\endgroup$ – user482594 Aug 28 '11 at 21:49
  • 1
    $\begingroup$ 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? $\endgroup$ – Niel de Beaudrap Aug 28 '11 at 21:54
  • 2
    $\begingroup$ If you don't remember calculus, then perhaps this course is not for you... At least discuss your predicament with the instructor. $\endgroup$ – GEdgar Aug 28 '11 at 22:00
  • $\begingroup$ 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. $\endgroup$ – Niel de Beaudrap Aug 28 '11 at 22:38

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

  • $\begingroup$ 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. $\endgroup$ – ItsNotObvious Nov 1 '11 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.