7
$\begingroup$

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

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Kevin
    Oct 24 '14 at 17:54
  • 1
    $\begingroup$ @Kevin The question says nothing at all about the number of operations required to compute anything: it just asks for the solution to a recurrence relation. Solutions to recurrences don't have to be running times to algorithms, just as numbers don't have to be lengths or weights. $\endgroup$ Oct 25 '14 at 0:10

Your Answer

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

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