6
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ All he said was "this is the definition of log(n)". $\endgroup$ – R.V. Apr 3 '17 at 6:48
  • 7
    $\begingroup$ @R.V. That's unfortunate because it is most definitely not the definition of $\log n$. (In particular, as $n\to\infty$ it tends to $\gamma + \log n$ for some constant $\gamma\approx 0.577$.) $\endgroup$ – David Richerby Apr 3 '17 at 8:03
  • 2
    $\begingroup$ Most of the answers why log(n) is in there, but the important part, from a time complexity point of view, is that the (Euler-Mascheroni) constant part is NOT included because it does not change as the input changes. Hence its O(log(n)), without the constant. $\endgroup$ – Evil Dog Pie Apr 3 '17 at 12:53
  • 2
    $\begingroup$ Please disprove your instructor's claim by showing that $1/1 \ne \ln(1)$, and for good measure $1/1+1/2 \ne \ln(2)$. $\endgroup$ – user21820 Apr 4 '17 at 8:36
19
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This is true but I suspect the asker's actual difficulty was in seeing the connection between the harmonic series and logarithms and probably isn't related to the disappearing constant. $\endgroup$ – David Richerby Apr 3 '17 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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