# What is the Big O of T(n)?

I have a homework that I should find the formula and the order of $T(n)$ given by

$$T(1) = 1 \qquad\qquad T(n) = \frac{T(n-1)}{T(n-1) + 1}\,.$$

I've established that $T(n) = \frac{1}{n}$ but now I am a little confused. Is $T(n) \in O(\frac{1}{n})$ the correct answer for the second part?

Based on definition of big-O we have that

$$O(g(n)) = \{f(n) \mid \exists c, n_0>0\text{ s.t. } 0\leq f(n) \leq cg(n)\text{ for all } n\geq n_0\}\,.$$

This holds for $f(n) = g(n) = \frac{1}{n}$ so, based on the definition, $O(\frac{1}{n})$ should be correct but, in the real world it's impossible that algorithm can be faster than $O(1)$.

Yes, all functions $f(n)$ satisfy $f(n) \in O(f(n))$. The definitions are meaningful even if $f(n)$ isn't the running time of any function. Indeed, this notation comes from number theory, where $f(n)$ is usually some error term. Even in computer science, sometimes big O notations is used while analyzing algorithms for something other than a running time or space requirements.
• It looks like the difference is that $T(n)$ grows with $\frac{1}{n}$ as $n$ increases, but the number of operations to calculate $T(n)$ is $O(1)$ if you simplify $T(n)$ to $T(n) = \frac{1}{n}$ or $O(n^2)$ if you use the definition provided in the homework problem directly. Oct 24, 2014 at 17:54