patternMinor
What is the Big O of T(n)?
Viewed 0 times
bigthewhat
Problem
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)$.
$$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)$.
Solution
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.
Context
StackExchange Computer Science Q#32269, answer score: 8
Revisions (0)
No revisions yet.