Finding tight bound for a function

Question

Suppose we are given a rational function $f(n)=\frac{p(n)}{q(n)}$ and need to find g(n) that satisfies: $f(n) \in \Theta(g(n))$. Does g(n) need to be one of $n^c, log n, n log n$ or can it be, in this case $g(n)=f(n)=\frac{p(n)}{q(n)}?$

Answer 1

Of course $f(n) \in \Theta(f(n))$ by definition of $\Theta$, but usually what the question is asking for is a simple function $g$. In this case you would only need the most significant term from the top and the bottom each. The proof of that goes like this:

For any $p(n) = a(n)+b(n)$ and $q(n) = c(n) + d(n)$ where $b(n) \in o(a(n))$ and $d(n) \in o(c(n))$ and $a(n) \ne 0$ and $c(n) \ne 0$,

  $\frac{p(n)}{q(n)} = \frac{a(n)}{c(n)} (1+\frac{b(n)}{a(n)}) (1+\frac{d(n)}{c(n)})^{-1} \in \frac{a(n)}{c(n)} (1+\frac{b(n)}{a(n)}) (1-O(\frac{d(n)}{c(n)}))$

  $\in \frac{a(n)}{c(n)} (1+o(1)) (1+o(1)) = \frac{a(n)}{c(n)} (1+o(1)) = \Theta(\frac{a(n)}{c(n)})$

Answer 2

Certainly if $g(n)=f(n)$ you have $f(n) \in \Theta(g(n))$ It is true, but often it will miss the point. The idea is to have $g(n)$ look like one of the things you cite to get an idea how it compares to other problems.