# Are big-theta, Big-O, etc. all representative only of GROWTH of the function?

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?

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

$2^{n-1}$ is that $\Theta(2^n)$?
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?
• In fact, $A=1/2$ and $B=1/2$ will work with all $n$ of any size. – GEdgar Jan 25 '14 at 16:56
$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.