snippetMajor
log(n) complexity. Difficulty understanding example
Viewed 0 times
understandinglogexampledifficultycomplexity
Problem
So, I am revisiting complexity analysis.
Here's the example: the instructor reduced an algorithm to:
n*(1 + 1/2 + 1/3 + ... + 1/n), and I can't seem to grasp why the part in parentheses is log(n).
Here's the example: the instructor reduced an algorithm to:
n*(1 + 1/2 + 1/3 + ... + 1/n), and I can't seem to grasp why the part in parentheses is log(n).
Solution
Do you know the Harmonic series (wiki)?
$$1 + \frac{1}{2} + \cdots + \frac{1}{n} = 1 + \sum_{i=2}^{n} \frac{1}{i} \le 1 + \int_{1}^{n} \frac{1}{x} \text{d}x = 1 + \ln n = \Theta(\log n).$$
Similarly, we also have
$$1 + \frac{1}{2} + \cdots + \frac{1}{n} = \sum_{i=1}^{n} \frac{1}{i} \ge \int_{1}^{n+1} \frac{1}{x} \text{d}x = \ln (n+1) = \Theta(\log n).$$
The formula above follows from
$$\int_{a}^{b+1} f(x) \text{d}x \le \sum_{i=a}^{b} f(i) \le \int_{a-1}^{b} f(x) \text{d}x$$
when $f(x)$ is non-increasing.
$$1 + \frac{1}{2} + \cdots + \frac{1}{n} = 1 + \sum_{i=2}^{n} \frac{1}{i} \le 1 + \int_{1}^{n} \frac{1}{x} \text{d}x = 1 + \ln n = \Theta(\log n).$$
Similarly, we also have
$$1 + \frac{1}{2} + \cdots + \frac{1}{n} = \sum_{i=1}^{n} \frac{1}{i} \ge \int_{1}^{n+1} \frac{1}{x} \text{d}x = \ln (n+1) = \Theta(\log n).$$
The formula above follows from
$$\int_{a}^{b+1} f(x) \text{d}x \le \sum_{i=a}^{b} f(i) \le \int_{a-1}^{b} f(x) \text{d}x$$
when $f(x)$ is non-increasing.
Context
StackExchange Computer Science Q#72400, answer score: 20
Revisions (0)
No revisions yet.