How to solve this recursion T (n) = T (n - 1) + log (1 + 1 / n), T (1) = 1?

Question

I am stuck in this repetition:

T(n) = T(n − 1) + lg(1 + 1/n), T(1) = 1?

and it seems that the master method cannot be applied to this.

Answer 1

We have:

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

Hence:

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

T(n-1) - T(n - 2) = lg(n) - lg(n - 1)

...

T(3) - T(2) = lg(3) - lg(2)

T(2) - T(1) = lg(2) - lg(1)

Adding and eliminating, we get:

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

or T(n) = 1 + lg(n + 1)

Hence, T(n) = O(lg(n))

Answer 2

The same answer as the other correct answer simply turned out to be different.

From this repetition, all of the following equations are created:

• T (n) = T (n-1) + Log ((n + 1) / n)
• T (n-1) = T (n-2) + Log (n / (n-1))
• .
• .
• .
• T (2) = T (1) + Log (3/2)

The summation of all RHS and LHS in the above equations leads to:

• T (n) = T (1) + Log (3/2) + Log (4/3) + ... + Log ((n + 1) / n)

Log (a) + Log (b) = Log (ab),

• T (n) = 1 + Log ((n + 1)/2)
• T (n) = Log (10) + Log ((n + 1)/2) = Log (5n + 5), , 10 1 = Log ₁₀ 10

, T (n) = O (log (5n + 5)) = O (Log (n))

Answer 3

, . O(log(n)). :

---

, :

,

:

:

, x → :

,

log(x + 1), O(log(n))