Does $\Theta(n^{-1}) = \Theta(1)$?

Question

I'm pretty sure that this is true for $O$, but not about $\Omega$ and $\Theta$.

@DonThousand $O(n^{-1}) = O(1)$ is true. – jjagmath Jul 09 '21 at 14:25 — jjagmath, Jul 09 '21 at 14:25

score 2 · Accepted Answer · answered Jul 09 '21 at 16:17

Interesting question! Here's my take on it, from my understanding of asymptotics:

Note that for a tight bound, $f(n)=\Theta(1)$ if there exist positive constants $c$ and $C$ such that for large enough $n$ we have $c\le f(n)\le C$.

For $O(1), C=1$ works as for large enough $n$, $\frac{k}{n}<1$ as the function $\frac{k}{n} \to 0, \forall$ values of $k.$

To prove $\Omega(1)$, you may try using $c=0$ as $\frac{k}{n}>0$, meaning that it is always lower bounded by $0$ (as it only approaches is as $n\to\infty$). However, $c$ must be positive, which is impossible as the function $\frac{k}{n}$is strictly decreasing for positive $n,k,$ and cannot be lower bounded by a positive constant.

So from what I understand, $\Theta(n^{-1}) ≠ \Theta(1)$.

PS—I'm only in high school so if someone has a correction then please comment it below! Cheers.

I don't think there is the need to use $k$ here. It would suffice to say $n^{-1} < 1$ for all $n>1$. The same holds for your proof that $n^{-1}$ is not $\Theta(1)$. — Giorgos Giapitzakis, Jul 09 '21 at 16:42

Does $\Theta(n^{-1}) = \Theta(1)$?

1 Answers1