So, I asked this question on a discrete structures exam today, which I apparently didn't give enough thought to:
$f(x) = (5x^2 + 6x + 2)/(x^3 + 4x^2 +x)$
Find the correct theta notation for the function.
So, I believe it is easy to create an upper bound around $1/x$ since we can show $f(x) \leq 2/x$ for sufficiently large $x$. I don't know that a lower bound can exist since $C$ must be positive and would need to be zero for a proper $\Omega(n)$ lower bound.
First, am I correct about the non-existence of a tight bound or am I missing something here?
Second, is this the only reason this is a Mickey Mouse type question or what else am I missing here? It seems like it could be possible for a particular algorithm to have a $1/x$ complexity.
Write $f(x) = g(x)/h(x)$, where $g(x)$ is the numerator and $h(x)$ is the denominator. Hopefully we can all agree that $g(x) = \Theta(x^2)$ and $h(x) = \Theta(x^3)$: for example, for $x \geq 1$ we have $$ 5x^2 \leq g(x) \leq 13x^2 \\ x^3 \leq h(x) \leq 6x^3 $$ It follows that $f(x) = \Theta(1/x)$: for example, for $x \geq 1$ we have $$ \frac{5}{6} \frac{1}{x} = \frac{5x^2}{6x^3} \leq \frac{g(x)}{h(x)} \leq \frac{13x^2}{x^3} = 13 \frac{1}{x}. $$ The same calculation we did here shows that (abusing notation) $\Theta(\alpha(x))/\Theta(\beta(x)) = \Theta(\alpha(x)/\beta(x))$, where in this case $\alpha(x) = x^2$ and $\beta(x) = x^3$.