Is log(n) time complexity possible of any recursive function? - Quora

Answer (1 of 4): It Depends. If the recursive function is C-recursive, or linear recursion with constant coefficients, then there are well known algorithms for computing the n-th term using O(log n) steps. Fibonacci Numbers, exponentials, and polynomials are all good examples. If the recursive ...