Given $T(n) = T(n-1) + \frac{1}{n}$, show that The Master Theorem is not applicable to this recurrence equation

Question

Given $$T(n) = T(n-1) + \frac{1}{n},$$ show that The Master Theorem is not applicable to this recurrence equation, hence show that $T(n)=O(\log n)$ using algebraic substitution given $T(1) =1$.

Answer 1

Part 1. You cannot apply the master theorem as the critical exponent is not well defined as the base of the logarithm would be essentially $1$.

Part 2. Hint: Using the substitution $T(1)=1$, you get $T(n)= \sum_{i=1}^n \frac{1}{i}$. Next use the property that $\lim_{n\to\infty} [ T(n)-\log(n) ]= \gamma$, where $\gamma$ is the Euler constant.