recurrence solving [closed]

Question

I need to find the complexity of the current recurrence:

T(n) = 1/(T(n-1) + 1) + 1

thanks in advance for any idea or link with useful information

Answer 1

Expanding on my comments above...

This doesn't make sense as a real-world recurrence relationship. T(n) denotes the runtime to solve a problem of size n; T(n-1) denotes the runtime for size (n-1). Given that you must solve the problem for size (n-1) before you can solve for size n (otherwise it wouldn't be a recursion), the runtime must necessarily be monotonic as n increases.

However, your expression oscillates up and down with n; this doesn't make sense.

The only way this expression could ever make sense is if we assume that T(n) is constant with n, so that there is no oscillation. It turns out that there is a constant value that allows this to happen, just set T(n) = T(n-1), and solve. (Note that this is equally meaningless; we don't generally talk about absolute values of T(n).)