# Big O notation comparison with constant time [duplicate]

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))$.

• Your second example is correct. How/why do you think the two are (not) analogous? – Tom van der Zanden Feb 5 '15 at 22:14
• 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 – dreamin Feb 5 '15 at 22:18
• – Raphael Feb 6 '15 at 7:52

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.