Using $\lim_{x \to \infty}$ to determine whether $f(x) = \Theta(g(x))$?

Question

I'm learning it in the context of Running time complexity.

to determine whether $f(x) = O(g(x))$, you can check whether the folloing limit:$$\lim_{x \to \infty} {f(x) \over g(x)} < \infty$$

if so, then you know that $f(x) = O(g(x))$.

Is there a similar way to determine whether $f(x) = \Theta(g(x))$?

Thanks in advance.

score 2 · Accepted Answer · answered Oct 17 '13 at 23:43

2

Actually, the Theorem that I know says that if $0 < \lim_{x \to \infty}f(x)/g(x) < \infty$, then $f(x) \in \Theta(g(x))$, which it turn implies that $f(x) \in O(g(x))$. I am currently TA-ing a course on Data Structures, and these are the slides that we are using: https://www.student.cs.uwaterloo.ca/~cs240/f13/modules/module01.pdf - If you look at slide 32/48, you'll see the theorem that I just mentioned.

answered Oct 17 '13 at 23:43

Nizbel99

907

I'm taking Data structures course either, I was sick this week and I couldn't go the lecture. thank you very much! – Billie Oct 17 '13 at 23:49
No problem! Glad to be of assistance. – Nizbel99 Oct 17 '13 at 23:54

Using $\lim_{x \to \infty}$ to determine whether $f(x) = \Theta(g(x))$?

1 Answers1