1
$\begingroup$

I have an expression which I think is $o(2^n)$, but I'm having difficulty simplifying it:

$o(2^n/n)\log(o(2^n/n) + n)$

I can ignore the extra $n$ sitting at the end, since $o(2^n/n) + n = o(2^n/n + n) = o(2^n/n)$, but then I can't say $\log(o(2^n/n)) = o(\log(2^n/n))$, can I? The rest would follow easily.

At least, it's not true in general that if $g(n)$ is $o(f(n))$ then $\log(g(n)) = o(\log(f(n)))$ (e.g., use $n$ and $n^2$). Is there some other way to do it? (Or is it plain not true?)

[EDIT] While it's not entirely relevant to the question, I suppose I should give the context. I'm working on an exercise from Gems of Theoretical Computer Science where you give a lower bound of $\Omega(2^n/n)$ on the circuit size of a boolean function generated from an incompressible string. So far, I have that if there are $g$ gates and $n$ variables, then the total circuit requires $g(c+2\log(g+n))$ bits to describe. Then supposing that the number of gates is $o(2^n/n)$, we should arrive that the total circuit description length (and hence the Kolmogorov complexity of the string) is $o(2^n)$, a contradiction.

  • 1
    You are correct, I was thinking $O$ not $o$. However, $o(1)$ does not have to be zero, it just has to tend to 0 as $n \to \infty$. For example $1/n = o(1)$ since $(1/n)/1 \to 0$ as $n \to \infty$.2012-04-22

2 Answers 2

1

Consider $a_n=\log(n+x_n)$ with $x_n=o(2^n/n)$. Since $\log(2^n/n)=n\log2-\log n=\Theta(n)$, our question is to know whether $a_n=o(n)$.

With no restriction on the sign of $x_n$, there is no hope. Assume for example that $x_n=-n+\mathrm e^{-y_n}$ with $y_n\to+\infty$. Then $x_n=-n+o(1)$ hence $x_n=o(2^n/n)$ but $a_n=-y_n$ hence $(a_n)$ may be any sequence such that $a_n\to-\infty$.

Even assuming that $x_n\geqslant0$ for every $n$, the conclusion that $a_n=o(n)$ is not guaranteed. For example, $x_n=2^{n/2}$ yields $x_n=o(2^n/n)$ and $a_n=n/2$, which is not $o(n)$. But for every nonnegative $(x_n)$, $\log n\leqslant a_n\leqslant n$ for every $n$ large enough, hence $a_n=O(n)$.

  • 0
    Aha! But this still works for my overall goal, since $o(2^n/n)O(n)$ is still $o(2^n)$. Thanks!2012-04-22
-1

I think the fact that this is $o(2^n/n)\log(o(2^n/n)+n)$ gives you a representation of f as $cn(2^n/n)\log (dn(2^n/n)+n)=cn(2^n)\log(dn(2^n/n)+n)/n$ and I think it's pretty clear if the dn go to 0 then $\log(dn(2^n/n)+n)/n$ is at LEAST bounded, and the cn go to zero yielding the whole thing as o(2^n).

  • 0
    I think I'm confused by your notation, what are the $cn$ and $dn$? Are those sequences?2012-04-22