# Theta notation from the inequality $c_1lg(n) \leq lg(k) \leq c_2lg(n)$ [duplicate]

Possible Duplicate:
tight bounds from a certain inequality

Consider the inequality

$$c_1lg(n) \leq lg(k) \leq c_2lg(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_1lg(n)} \leq 2^{lg(k)} \leq 2^{c_2lg(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})$?

-

## marked as duplicate by Did, Jennifer Dylan, tomasz, D'oh, QuixoticSep 9 '12 at 15:22

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

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