1
$\begingroup$

Consider the inequality

$ c_1\lg(n) \leq \lg(k) \leq c_2\lg(n),\text{ for } n \geq n_{0} $

With $c_1,c_2,n_0 > 0$, $\lg(k) = \Theta(\lg(n))$

By deriving the actual relationship of $k$ with $n$, we have

$ \Rightarrow 2^{c_1\lg(n)} \leq 2^{\lg(k)} \leq 2^{c_2\lg(n)}\\ \Rightarrow 2^{\lg(n^{c_1})} \leq 2^{\lg(k)} \leq 2^{\lg(n^{c_2})}\\ \Rightarrow n^{c_1} \leq k \leq n^{c_2} $

If $c_1 \neq c_2$, is it still possible to provide tight bounds (e.g. Theta notation) for $k$ given that $k = \Omega(n^{c_1})$ and $k = O(n^{c_2})$?

  • 1
    No, nothing more precise than $\Omega(n^{c_1})$ and $O(n^{c_2})$.2012-03-01

1 Answers 1

1

Consider $n$, $n^2$ and $n^3$.

We have that $\log n^2 = \theta(\log n)$ but, $n^2 \neq \theta(n^3)$ and $n^2 \neq \theta(n)$.

Does that answer your question?

  • 0
    yes, I think cases where $lg(k) = \Theta(lg(n)) \Rightarrow k = \Theta(n)$ are only rare and must not be used for generalization.2012-03-01