Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 1 down vote favorite

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

share|improve this question
1  
No, nothing more precise than $\Omega(n^{c_1})$ and $O(n^{c_2})$. – Did Mar 1 '12 at 7:20
Related: math.stackexchange.com/questions/114846/… – Henry Mar 1 '12 at 7:33

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1 Answer

up vote 1 down vote accepted

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?

share|improve this answer
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

Not the answer you're looking for? Browse other questions tagged or ask your own question.