log(n) complexity. Difficulty understanding example

Question

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).

Answer 1

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.

Answer 2

$1 + \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{n}= \sum_{i=1}^{n} \frac{1}{i}=H_n$ where $H_n$ is the $n^{th}$ harmonic number.

So inside the parenthesis you don't have $\log(n)$.

But, what can be proved is that:

• $\ln(n+1) < H_n \le 1 + \ln(n)$
• $H_{n+1} - \ln(n+1) < H_n - \ln(n)$

so that the $H_n - \ln(n) \ge 0$ and the difference decreases.

Example:

\begin{align*} H_1 - \ln(1) &= 1\\ H_2 - \ln(2) &= 0.80...\\ H_3 - \ln(3) &= 0.73...\\ &\;\;\vdots\\ H_{10} - \ln(10) &= 0.62..\\ &\;\;\vdots\\ H_{100} - \ln(100) &= 0.58... \end{align*}

The limit tends to a constant called the Euler-Mascheroni constant $$\lim_{n\to\infty} (H_n - \ln(n))=0.577...$$

So, to conclude, $H_n = \Theta(\log n)$.

Answer 3

"All he said was 'this is the definition of $\log n$'". That's sad. Because it's wrong, and because your instructor should be helping you, and this isn't helpful.

If your maths isn't very strong, here's a simpler method to see what's going on:

You have a sum $1 + 1/2 + 1/3 + \dots + 1/n$. That's one term $= 1$, one term $= 1/2$. Then two terms $1/3$ and $1/4$, both $\geq 1/4$, so their total is $\geq 1/2$. Then four terms $1/5$, $1/6$, $1/7$, $1/8$, all four $\geq 1/8$, so their total is $\geq 1/2$. Then eight terms up to $1/16$ add up with a total $\geq 1/2$, and so on. If you do the sum up to $n = 2^k$ then you added the number $1$, and $k$ times the number $1/2$. The sum is $\geq 1 + k/2$.

On the other hand, $1/3$ and $1/4$ are $\leq 1/2$ so they add to a total $\leq1$. $1/5$ to $1/8$ are each $\leq 1/4$, so they add to a total $\leq 1$. The terms $1/9$ to $1/16$ are $\leq 1/8$, so their total is $\leq 1$. If you sum everything up to $n = 2^k$, the total sum is $\leq 1/2 + k$.

So the sum up to $n = 2^k$ is between $1 + k/2$ and $1/2 + k$, or between $1 + (\log_2 n) / 2$ and $1/2 + \log_2 n$, which is $\Theta (\log n)$.

Answer 4

Using Stolz-Cesàro:

$$ \lim_{n\to\infty}\frac{1 + 1/2 + \cdots + 1/n}{\log n} = \lim_{n\to\infty}\frac{1/(n + 1)}{\log(n + 1) - \log n} = \lim_{n\to\infty}\frac{1/(n + 1)}{\log(1 + 1/n)} = \lim_{n\to\infty}\frac{1/(n + 1)}{1/n} = 1, $$ so $H_n = \Theta(\log n)$.

Answer 5

The important part to understand is that the time complexity of an algorithm (when expressed using big O notation) excludes coefficients and lower order terms.

Other answers have shown where the log(n) term comes from, but your instructor is absolutely correct to leave out the constant part of the expression when stating the time complexity of the algorithm.