0
$\begingroup$

Let's say we have $3^{4n}$ and $4^{3n}$. With the note of The Asymptotic Cheat Sheet from MIT.

We should first calculate the lim n->infinity $3^{4n}$/$4^{3n}$. and it result is $\infty$.

In the we have

lim n→∞ f(n)/g(n) != 0,∞  ⇒  f=Θ(g)   Note 1

and

lim n→∞  f(n)/g(n)=∞     ⇒ f=ω(g)   Note 2

My questions is: Given that f(n) is $3^{4n}$ and g(n) is $4^{3n}$ in this case, which "case" should we apply ? How should one read Note 1 correctly ? Does it mean "lim n→∞ f(n)/g(n) not equal to 0, but equal to infinity? then f=Θ(g) " Or
"lim n→∞ f(n)/g(n) not equal to 0 and not equal to infinity, then f=Θ(g)?

Also if f(n) = $\theta $ g(n)? doesn't that already mean f(n) = $O$ g(n)? if so, then note 1 should read as "lim n→∞ f(n)/g(n) not equal to 0 and not equal to infinity, then f=Θ(g)?

$\endgroup$
0
$\begingroup$

Knowing $3^4=81$ and $4^3=64$, we have $f(n)=81^n$ and $g(n)=64^n$. Using this we obtain: $$\lim\limits_{n \to \infty}\frac{f(n)}{g(n)}=\lim\limits_{n \to \infty}\left(\frac{81}{64}\right)^n=+\infty$$ so you have your "Note 2". By definition last limit mean $\forall C>0$ we have $\exists N \in \mathbb{N}$, such that $\forall n>N$ holds $\frac{f(n)}{g(n)} \geqslant C$ so we have $f\in \Omega(g)$.

For further let's assume, that we have positive functions and $g$ have not $0$s subsequence.

Following question. Your "note 1" means that $\lim\limits_{n \to \infty}\frac{f(n)}{g(n)}$ is not $0$ and is not $\infty$, but equals to some number between them.

And last. Suppose $\lim\limits_{n \to \infty}\frac{f(n)}{g(n)}=A>0$. This means, that $A-\varepsilon<\frac{f(n)}{g(n)} < A+\varepsilon$, for appropriate $n$, and so we can conclude $f \in \Theta(g)$.

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