1
$\begingroup$

I saw a similar question to this one here but it's not quite the same as mine:

Is every algorithm's complexity $\Omega(1)$ and $O(\infty)$?

I've just started a course in data structures and introduction to algorithms and there's a question on a homework assignment whose answer is a little unclear to me:

Given $f:\mathbb{N}\rightarrow\mathbb{R}^+$, prove or disprove $f(n) = \Omega(1)\ \ $.

I'm a little conflicted about this because on one hand, I know that $\Omega(1)$ is the set of all functions $f$ for which there exist some $c,n_0\in\mathbb{R}^+$ such that for every $n > n_0 \in\mathbb{N}$, $f(n) \geq c$ . So wouldn't $f(n) = \frac{1}{n}$ not be considered an element in that set? No matter how we choose the positive constant $c$ there will always be some $n$ where $f(n) < c$ since $f(n)$ gets smaller as $n$ gets larger.

On the other hand, this is a computer science course and I'm not aware of an algorithm whose complexity is $\Theta(\frac{1}{x})$ so perhaps I'm overthinking this?

$\endgroup$
  • $\begingroup$ If the number of executed statements is $n + 10^{100} \cdot x^{-1}$, you'll want to know about the vanishing term. $\endgroup$ – Raphael Mar 13 '18 at 12:39
  • $\begingroup$ As you say, any function not bounded below by a positive constant is not $\Omega(1)$. One example is the zero function; another is $\frac{1}{n}$. Note that any algorithm besides the "trivial algorithm" that exits immediately always performs at least one operation so a function that is the time complexity of a non-trivial algorithm is $\Omega(1)$. (Note that an algorithm can't perform some instructions on some inputs but no instructions on other inputs as such an algorithm would have to perform an instruction to examine the input to know whether to perform an instruction...) $\endgroup$ – Solomonoff's Secret Mar 13 '18 at 15:17
  • $\begingroup$ I understand, thank you both so much! $\endgroup$ – Or Bairey-Sehayek Mar 13 '18 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.