0
$\begingroup$

For example,

$2^{n-1}$... is that $\Theta(2^n)$?

it GROWS the same... but it in actuality will never be greater than or equal to the actual 2^n function, for example.

$\log_2(n)$, is that $\Theta(\log_4(n))$?

How do we handle growth of logarithm with different bases when describing things in these notations?

How about this:

$2^{n^2}$, is that $O(2^n)$?

How about exponentials on the nth term? Are these ignored like constants?

Just trying to understand the semantics of these notations in practicality.

$\endgroup$
0
$\begingroup$

$2^{n-1}$ is that $\Theta(2^n)$?

hint
You need to show that (for large enough $n$) there are constants $A,B$ so that $$ A 2^n \le 2^{n-1} \le B 2^n . $$ Can you do that?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Let's say my "large enough n" is 2. Le't's say my constants A and B are 1/2000 and 2000. With that - the expression above evaluates. But is that truly all we need to evaluate? What defines "large enough n"? $\endgroup$ – PinkElephantsOnParade Jan 25 '14 at 16:49
  • $\begingroup$ In fact, $A=1/2$ and $B=1/2$ will work with all $n$ of any size. $\endgroup$ – GEdgar Jan 25 '14 at 16:56
0
$\begingroup$

$g(n)=\Theta(f(n))$ means "there exists two constants $\alpha,\beta>0$ and an integer $N$ such that $\forall n \geq N$, $\alpha f(n)\leq g(n) \leq \beta f(n)$. So yes to your two first questions.

$g(n)=O(f(n))$ means "there exists a constant $\alpha>0$ and an integer $N$ such that $\forall n \geq N$, $g(n) \leq \alpha f(n)$. So no to your last one.

| cite | improve this answer | |
$\endgroup$

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.