0
$\begingroup$

So, I'm new to this whole asymptomatic notation with respect to algorithms. So say you have a $f(n) = 1/n$ and $g(n) = 1$, would it be OK to say that $f(n)$ is not equal or is not an element of $O(g(n)) $? I say this because I'm actually drawing an analogy with another example. Say in my second example $f(n) = n$ and $g(n) =n^2$ then I'm sure that $f(n) = O(g(n))$.

$\endgroup$
  • $\begingroup$ Your second example is correct. How/why do you think the two are (not) analogous? $\endgroup$ – Tom van der Zanden Feb 5 '15 at 22:14
  • $\begingroup$ Just because a lot of times I find myself learning by previous examples. But I also think that $f(n)$ is not equal because $O(1)$ is constant time $\endgroup$ – dreamin Feb 5 '15 at 22:18
  • $\begingroup$ Also related. $\endgroup$ – Raphael Feb 6 '15 at 7:52
1
$\begingroup$

In fact, $1/n = O(1)$. Recall the (simplified) definition of big O: for positive functions $f,g$, $f(n) = O(g(n))$ if there exists a constant $C > 0$ such that $f(n) \leq Cg(n)$ for all $n$. In your case, the constant $C = 1$ would do since $1/n \leq 1$ for all $n$.

The fact that $f(n) = O(g(n))$ just means that $g(n)$ is an upper bound on $f(n)$, i.e., that $g(n)$ grows at least as fast as $f(n)$. The two functions need not have the same order of growth.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.