2
$\begingroup$

I was going across some problems which translated the fact that $\log (n!) = \Theta(n\log n)$ to give $$\log(\lceil\log n\rceil!) = \Theta(\lceil\log n\rceil \log \lceil\log n\rceil)$$ and therefore $\log(\lceil \log n\rceil!) = \omega(\lg n)$.

Now I just have this intuition that this sort of conversions shouldn't and wouldn't be always right.

Would it be right to think that.

Any justification as to why am I wrong in thinking that and guidance to what I should have a look at, what texts I should go through to understand it better for myself are very much appreciated.

Thank you.

$\endgroup$
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Sep 15 '16 at 17:07
  • $\begingroup$ See bullet two here. $\endgroup$ – Raphael Sep 15 '16 at 17:08
6
$\begingroup$

In general, you can prove nothing. You know $f(n) = \Theta(g(n))$. Now assume f (n) = g (n) = n for all n except g (n) = 0 if n ≤ 1000. And h (n) = 1000 for all n.

So we now have f (h (n)) = 1000 and g (h (n)) = 0.

The problem is that $O (n)$ and $\Theta (n)$ only work for large n. You are fine if h (n) -> inf, or if you look specifically at f (n) and h (n).

If the limit of h (n) is infinity, then you overcome the problem that $\Theta(g(n))$ only gives you information for n ≥ N for some possibly large N, because h (n) will eventually be greater than that N.

$\endgroup$
  • $\begingroup$ I get your point. Just couldn't understand the last part ! h(n) -> inf ?. $\endgroup$ – ps_ Sep 16 '16 at 2:42
2
$\begingroup$

Why would there be a problem? You know that $\log (t!) = \Theta(t\log t)$. Why would it matter whether you call the thing $t$ or $\lceil\log n\rceil$? (As long as you can make $\lceil\log n\rceil$ large enough for the asymptotic relationship to kick in; and you can.)

$\endgroup$
  • $\begingroup$ I'm not aware of formal proofs for claims stronger than bullet two here. $\endgroup$ – Raphael Sep 15 '16 at 17:11
2
$\begingroup$

Below, I'm assuming that the domain of all function is the non-negative reals.

By definition, $f(n) = \Theta(g(n))$ if there exist $N \geq 0$ and $A,B > 0$ such that $$ n \geq N \Longrightarrow A g(n) \leq f(n) \leq B g(n). $$ If there exists a constant $c > 0$ such that $f(n),g(n) \geq c$ for all $n$ and $f,g$ are continuous, then we can in fact take $N = 0$ (perhaps modifying $A,B$ in the process). This means that for all $n$, it holds that $$ A g(n) \leq f(n) \leq B g(n). $$ Assuming that $h(n) \geq 0$ for all $n$, this implies that $$ A g(h(n)) \leq f(h(n)) \leq B g(h(n)), $$ and so $f(h(n)) = \Theta(g(h(n))$.

Even without assuming that $N = 0$, we can make the same conclusion if $\lim_{n\to\infty} h(n) = \infty$. In that case, there exists $M$ such that $n \geq M$ implies $h(n) \geq N$, and so $$ n \geq M \Longrightarrow A g(h(n)) \leq f(h(n)) \leq B g(h(n)), $$ again implying $f(h(n)) = \Theta(g(h(n))$.

$\endgroup$
  • $\begingroup$ I haven't gone through the details, but I think there are some subtleties involved. Compare with bullet two here, a statement we found a rigorous proof for (but not for stronger claims). $\endgroup$ – Raphael Sep 15 '16 at 17:10

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.