0

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.

2012ssohn
  • 3,827
PinkElephantsOnParade
  • 317

2 Answers2

0

$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.

Clement C.
  • 67,323
0

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

GEdgar
  • 111,679
  • 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"? – PinkElephantsOnParade Jan 25 '14 at 16:49
  • In fact, $A=1/2$ and $B=1/2$ will work with all $n$ of any size. – GEdgar Jan 25 '14 at 16:56