0
$\begingroup$

Assume this recurrence: $$T(n)=T(n-1)+\frac{1}{n}$$

As we can use Master Theorem and Akra-Bazzi method here, I tried to draw a recurrence tree and I reached the whole cost of this tree is $\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{n}$. What's a tight upper and lower bound for this recurrence (I'm talking about $\Theta$, not $\mathcal{O}$)? Is it even possible to find a $\Theta$ for it?

$\endgroup$

1 Answer 1

2
$\begingroup$

The quantity $H_n = \sum_{i=1}^n \frac{1}{i}$ is known as the $n$-th harmonic number. It is well-known that $H_n = \Theta(\log n)$.

To see this notice that the function $\frac{1}{x}$ is monotonically decreasing, which means that the area under $\frac{1}{x}$ in the range $i \le x \le i+1$ is at most $\frac{1}{i}$ (i.e. the area of a rectangle of width $i+1 - i = 1$ and height $\frac{1}{i}$). In formulas: $\int_{i}^{i+1} \frac{1}{x} \text{d}x \le \int_{i}^{i+1} \frac{1}{i} \text{d}x = \frac{1}{i}$.

$$ H_n = \sum_{i=1}^n \frac{1}{i} \ge \sum_{i=1}^n \int_{i}^{i+1} \frac{1}{x} \text{d}x = \int_{1}^{n+1} \frac{1}{x} \text{d}x = \ln (n+1) = \Omega( \log n). $$

Similarly, the area under $\frac{1}{x}$ in the range $i \le x \le i+1$ is at least $\frac{1}{i+1}$, i.e., $\int_{i}^{i+1} \frac{1}{x} \text{d}x \ge \int_{i}^{i+1} \frac{1}{i+1} \text{d}x = \frac{1}{i+1}$.

$$ H_n = 1 + \sum_{i=1}^{n-1} \frac{1}{i+1} \le 1 + \sum_{i=1}^{n-1} \int_{i}^{i+1} \frac{1}{x} \text{d}x = 1 + \int_{1}^{n} \frac{1}{x} \text{d}x=1+\ln n = O(\log n). $$

$\endgroup$
3
  • $\begingroup$ Thanks. Can you please write or link a proof to it? $\endgroup$ Nov 14, 2023 at 14:50
  • $\begingroup$ In the last line, is it $O(n)$ or $O(\log{n})$? $\endgroup$ Nov 14, 2023 at 15:08
  • $\begingroup$ @IlkayBurak, clearly it is $O( \log n)$. Thanks for pointing out the typo :) $\endgroup$
    – Steven
    Nov 14, 2023 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.