I'm fairly certain that if f(n) = Θ(g(n)) is true, if f(n) is asymptotically equal to g(n). However, I'm concerned I might be overlooking something. Am I correct in thinking that f(n) = Θ(g(n)) then f(n) is asymptotically equal to g(n)? or am I overlooking something?
I'm trying to compare different algorithms with respective runtimes of f(n) and g(n) and prove that f(n) = Θ(g(n)), but I'm not sure if I'm on the right way or not.
A. f(n) = log(n^00), g(n) = log(n^2)
lim n->∞ f(n)/g(n) = lim n->∞ log(n^200)/log(n^2) = 100
Since the result is a constant, we conclude that f(n) ∈ ϴ(g(n)), hence f(n) = ϴ(g(n)).
B. f(n) = sqrt(n), g(n) = log(n)
lim n->∞ f(n)/g(n) = lim n->∞ sqrt(n)/log(n) = ±∞, in my case ∞, hence f(n) ≠ ϴ(g(n)).
C. f(n) = 3^n, g(n) = 5^n
lim n->∞ f(n)/g(n) = lim n->∞ 3^n/5^n = 0, hence f(n) ≠ ϴ(g(n)).
D. f(n) = sin(n)+3, g(n) = cos(n)+1
lim n->∞ f(n)/g(n) = lim n->∞ sin(n)+3/cos(n)+1 = 4/3, hence f(n) ≠ ϴ(g(n)).
Please tell me, am I on the right way?
Let's assume, that we are using Asymptotic equality definition i.e., as is written in comment, $\lim\limits_{n\to\infty}\frac{f(n)}{g(n)}=1$, which we denote by $f\sim g$. On another hand for $f(n)=\Theta(g(n)), n\to\infty$ we have definition (taking non-negative case) $$\Theta(g(n))= \{\phi: \exists c_1,c_2>0, \exists N\in\mathbb{N},\forall n>N, c_1 g(n)\leqslant \phi (n) \leqslant c_1 g(n)\}$$.
As simple counterexample we can consider $f(n)=g(n)=0$, for $\forall n$. Obviously $f(n)=\Theta(g(n))$, but we cannot consider fraction $\frac{f(n)}{g(n)}$. As to your examples, then some are bad formatted, some simply wrong, so let me leave them without comment.