# Theta notation from $\DeclareMathOperator{\lg}{lg}$the inequality $c_1\lg(n) \leq \lg(k) \leq c_2\lg(n)$

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})$?

-
No, nothing more precise than $\Omega(n^{c_1})$ and $O(n^{c_2})$. – Did Mar 1 '12 at 7:20

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)$.
yes, I think cases where $lg(k) = \Theta(lg(n)) \Rightarrow k = \Theta(n)$ are only rare and must not be used for generalization. – edgar Mar 1 '12 at 7:25