Explanation of summation equation

Question

Could somebody please explain the following equation to me?

I have no clue what H represents, nor how theta(ln(n)) - theta(ln(k)) results in theta(ln (n/k))

Any explanation would be appreciated.

Thanks!

Answer 1

The $H$ notation used is more a shorthand for the harmonic series' partial sums. More explicitly,

$$H(n) = \text{(the n-th partial sum of the harmonic series)} = \sum_{k=1}^n \frac{1}{k}$$

Edit: You could also say that $H(n)$ is the $n^{th}$ harmonic number, as the definition is the same.

Going from there, I'm just guessing on what $\Theta$ represents from what I could Google up. My guess is that it is a function that means "on the order of" or something of the sort. For that, it might be important to note that we can represent the harmonic series in a sort of "closed" form:

$$\sum_{k=1}^n \frac{1}{k} = \ln(n) + \gamma + \epsilon_n \approx \ln(n)$$

In this context, $\gamma$ is the Euler-Mascheroni constant, and $\epsilon_n$ is a sort of "error constant" that establishes the equality. It is proportional to $1/2n$ and thus $\epsilon_n \to 0$ as $n \to \infty$.

And then I guess because $\ln(n) - \ln(k) = \ln(n/k)$ per a property of logarithms, that might explain your other question.

But I want to emphasize that I'm kinda just guessing here since I'm not particularly familiar with the big-theta notation or how to utilize it. I think that's what's at play here, but it's just a guess.