1
$\begingroup$

As part of my continual improvement plans, I'm reviewing algorithm analysis and I've hit a roadblock. I cannot figure out how to determine the Big O complexity of $\log(n+7)^{\log(n)}$. I've spent the last few days rolling this over in my head and I still haven't made any progress in solving it. Could someone tell me what the Big O of this algorithm is, and explain how you solved it?

$\endgroup$
  • 3
    $\begingroup$ It's $O(\log(n+7)^{\log(n)})$, obviously. Any function can go inside $O(~)$. $\endgroup$ – JeffE Aug 26 '13 at 2:36
  • 1
    $\begingroup$ Also, $O(n^n)$. Please see here and improve your question. $\endgroup$ – Raphael Aug 26 '13 at 8:31
11
$\begingroup$

If you meant what $\mathcal{O}((\log (n+7))^{\log (n)})$ is (so the power applies to the logarithm itself, not its argument), then we simplify that to $\mathcal{O}((\log (n))^{\log (n)})$; as per a suggestion by Saeed Amiri, here a proof for this equality:

Since $(\log (n))^{\log (n)}) \leq (\log (n+7))^{\log (n)})$ for all $n$, we have $\mathcal{O}((\log (n))^{\log (n)}) \subseteq \mathcal{O}((\log (n+7))^{\log (n)})$.

For the other direction, consider

$\qquad \begin{align} (\log (2n))^{\log (n)} &\leq c(\log (n))^{\log(n)} &\iff \\ \frac{\log(2n)}{\log(n)} &\leq \sqrt[\log(n)]{c} &\iff \\ 1+\frac{\log(2)}{\log(n)} &\leq \sqrt[\log(n)]{c} &\iff \\ \left(1+\frac{\log(2)}{\log(n)}\right)^{\log(n)} &\leq c \end{align} $

What we now notice is that $\log n$ is a non-integer bound, so we can't directly expand to a polynomial here. We could if we knew that

$\left(1+\frac{\log(2)}{\log(n)}\right)^{\log(n)} \leq \left(1+\frac{\log(2)}{\lceil\log(n)\rceil}\right)^{\lceil\log(n)\rceil}$

Therefore, a small proof of the monotonicity of that function:

$\frac{d}{dx}\left(1+\frac{\log(2)}{\log(x)}\right)^{\log(x)} = \frac{\left(\frac{\log (2x)}{\log (x)}\right)^{\log (x)}\left(\log (2x)\log\left(\frac{\log (2x)}{\log (x)}\right) - \log (2)\right)}{x \log (2x)} \geq \frac{\log (2x)\log\left(\frac{\log (2x)}{\log (x)}\right) - \log (2)}{x (\log (x))^{\log (x)}} > 0$

for all $x > x_0$ for some $x_0$ [specifically, for $x_0 = 2$; check the link to math in the comment section].

Since we now know that the function is monotonically nondecreasing for all $n > 2$, we can choose our $c$ slightly differently:

\begin{align} \left(1+\frac{\log(2)}{\log(n)}\right)^{\log(n)} \leq \left(1+\frac{\log(2)}{\lceil\log(n)\rceil}\right)^{\lceil\log(n)\rceil} &\leq c &\overset{\text{rewriting the polynomial}}{\iff} \\ \sum_{i=0}^{\lceil\log(n)\rceil}\binom{\lceil\log(n)\rceil}{i}\left(\frac{\log(2)}{\lceil\log(n)\rceil}\right)^i &\leq c \end{align}

Now we use the inequality $\binom{n}{k} \leq \frac{n^k}{k!}$ and see that \begin{align} \sum_{i=0}^{\lceil\log(n)\rceil}\binom{\lceil\log(n)\rceil}{i}\left(\frac{\log(2)}{\lceil\log(n)\rceil}\right)^i &\leq \sum_{i=0}^{\lceil\log(n)\rceil}\frac{(\lceil\log(n)\rceil)^i}{i!}\left(\frac{\log(2)}{\lceil\log(n)\rceil}\right)^i \\ &= \sum_{i=0}^{\lceil\log(n)\rceil}\frac{(\log(2))^i}{i!} \\ &\leq \sum_{i=0}^{\infty}\frac{(\log(2))^i}{i!} \\ &= e^{\log(2)} \end{align}

So we know that $\mathcal{O}((\log (n+7))^{\log (n)}) \subseteq \mathcal{O}((\log (n))^{\log (n)})$ since we can choose a finite $c$ in the above inequation.


If we try to express $(\log (n))^{\log (n)}$ as a power of $n$ now, we get

\begin{align} n^{f(n)} &= (\log (n))^{\log(n)} &\iff \\ \log(n^{f(n)}) &= \log ((\log (n))^{\log(n)}) &\iff \\ f(n) \cdot \log(n) &= \log(n) \cdot \log (\log (n)) &\iff \\ f(n) &= \log (\log (n)) \end{align}

, and so we get $\mathcal{O}((\log (n))^{\log (n)}) = \mathcal{O}(n^{\log(\log(n))})$, if that is any improvement.

(Credit where it's due: I copied this way of expressing our function as a power of $n$ from here, so google can help with this stuff, sometimes.)


Now where does this place $\mathcal{O}((\log n)^{\log n})$ in terms of complexity? We know that $\forall c \in \mathbb{R}: \lim_{n \to \infty} \frac{c}{\log \log n} = 0$, which means that $n^c \in \mathcal{o}((\log n)^{\log n}) = \mathcal{o}(n^{\log \log n})$; the small $\mathcal{o}$ is intended here, it means that $n^c$ grows strictly slower than $n^{\log \log n}$. [A small remark about that at the end of all this; if this is not relevant to your needs or confuses you, you can - apart from those in the remark at the end itself - replace every $\mathcal{o}$ with $\mathcal{O}$, all statements will still be true.]

On the other hand, we have for any constant base $b > 1$:

\begin{align} n^{\log \log n} &\leq b^n &\iff \\ (\log \log n) * (\log n) &\leq n * \log b \end{align}

This tells us that instead of $n^{\log \log n}$ and $b^n$, we can equivalently compare $(\log \log n) * (\log n)$ and $n$ by just ignoring the constant (!) factor $\log b$. Using the limit rules for asymptotic notation as well as l'Hôpital's rule, we get

\begin{align} \lim_{n \to \infty} \frac{(\log \log n) * (\log n)}{n} &\leq \lim_{n \to \infty} \frac{(\log n) * (\log n)}{n} \\ &\overset{\text{l'Hôpital}}{=} \lim_{n \to \infty} \frac{2*\log n}{n} \\ &\overset{\text{l'Hôpital}}{=} \lim_{n \to \infty} \frac{2}{n} = 0 \end{align}

Therefore we know $(\log n)^{\log n} = n^{\log \log n} \in \mathcal{o}(b^n)$ for any base $b>1$ of the exponential, meaning it grows strictly slower than any exponential function with constant base that we would be interested in. (What I mean by this is that in the analysis of the complexity of algorithms, we don't care about exponentials with negative bases because those aren't even real functions, much less functions over the naturals, or exponentials with bases between $0$ and $1$ because those all converge to $0$.)

In summary, we now know that in terms of complexity:

\begin{align} \mathcal{O}(n^c) \subsetneq \mathcal{O}((\log n)^{\log n}) = \mathcal{O}(n^{\log \log n}) \subsetneq \mathcal{O}(b^n) \end{align}

for any constants $c > 0$ and $b > 1$. What you have is a function strictly between polynomial and exponential growth.


Now the remark about Big-Oh and small-oh: $\mathcal{o}$ is a stronger statement than $\mathcal{O}$, because if $f(n) \in \mathcal{o}(g(n))$ then we know $g(n)$ grows strictly (meaning by a non-constant factor) faster than $f(n)$, but if $f(n) \in \mathcal{O}(g(n))$ we only know that $g(n)$ grows at least as fast as $f(n)$, so there may only be a constant factor. For example, $n \in \mathcal{o}(n \log n)$ and $n \in \mathcal{O}(n)$, but $n \not \in \mathcal{o}(n)$.

$\endgroup$
  • $\begingroup$ let us continue this discussion in chat $\endgroup$ – user742 Aug 25 '13 at 18:15
  • $\begingroup$ Could you explain how this relates to a simpler, more common function? In other words, is log(n)^(log(n)) = O(n)? That's the gap in my understanding that I can't seem to fill.The textbook I have says that a polynomial always dominates a logarithm. However, the logarithms used in examples are always to a constant power. Does this general rule hold when the power is a variable? $\endgroup$ – Bobby Vandiver Aug 28 '13 at 21:18
  • $\begingroup$ @user1743952 Note that your question is utterly underspecified in this regard. Asking "what is its O-class?" is nearly meaningless (as the comments try to point out); you should say which functions are acceptable as bounds. $\endgroup$ – Raphael Aug 29 '13 at 14:32
  • $\begingroup$ @Raphael I think asking this follow up in a comment is alright, and I doubt there are meaningful bounds better than "superpolynomial, but subexponential" for this. $\endgroup$ – G. Bach Aug 29 '13 at 14:45
  • $\begingroup$ @user1743952 I'm also adding a proof that the expansion of the exponential is valid; if that is more math than you would like to stomach, you can just ignore it, my answer is valid as it stands. I just wanted to add it for completeness and my own peace of mind, so to speak. $\endgroup$ – G. Bach Aug 29 '13 at 17:40
3
$\begingroup$

I assume that the power is applied to the argument.

Following the lines of G.Bach's answer you can bound your expression as follows. For a sufficiently large $n$ we have $$\log(n+7)^{\log(n)}<\log(2n)^{\log n}=\log(2^{\log n }\cdot n^{\log n }) =\log 2^{\log n }+\log n ^{\log n}<2 \log n ^{\log n}.$$

This can be simplified as follows

$$\log n ^{\log n }=\log n \log n = \log^2n.$$

So a reasonable upper bound is $O(\log^2 n)$.

$\endgroup$

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.