If f(n) = Θ(g(n)) does that f(n) is asymptotically equal to g(n)?

Question

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^100), 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?

lim(f/g) in D is not 4/3. It has no limit (and isn't even bounded). — Paul Hankin, Sep 30 '22 at 09:08
The rule you're using (lim f/g is a non-zero constant) is a sufficient but not necessary condition for f=Theta(g)). For example (n%2+1) is Theta(1), but the limit doesn't exist. — Paul Hankin, Sep 30 '22 at 09:15

score 0 · Answer 1 · answered Sep 30 '22 at 06:36

Am I correct in thinking that if f(n) = Θ(g(n)) then f(n) is asymptotically equal to g(n)?

No, asymptotic equality is a stronger claim than asymptotically bound. The opposite is true: when () is asymptotically equal to (), then () is Θ(())

As defined on Wikipedia - Asymptotic Analysis:

if and only if
     ()
lim  ──── = 1 
→∞  ()
the functions and are said to be asymptotically equivalent.

For the first example where () = log¹⁰⁰ and () = log², this equivalence does not hold:

log¹⁰⁰ / log² = log¹⁰⁰ − log² = log⁹⁸, whose limit diverges to infinity and so () and () are not asymptotically equal.

See also Wikipedia - Family of Bachmann–Landau notations

If f(n) = Θ(g(n)) does that f(n) is asymptotically equal to g(n)?

1 Answers1