Problem Detail: I have a homework that I should find the formula and the order of $T(n)$ given by $$T(1) = 1 qquadqquad 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>0text{ s.t. } 0leq f(n) leq cg(n)text{ for all } ngeq 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)$.
Asked By : Karo
Answered By : Yuval Filmus
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/32269
