1
$\begingroup$

Could somebody please explain the following equation to me? enter image description here

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!

$\endgroup$
  • $\begingroup$ H indicates the harmonic numbers $\endgroup$ – G Cab Dec 7 '18 at 0:56
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, $\Theta$ basically means "on the order of", i.e., bounded both above and below up to a constant. See Big-O-notation $\endgroup$ – Jair Taylor Dec 7 '18 at 1:05
  • $\begingroup$ This was an absolutely amazing explanation. Thank you so much for taking the time to explain this to me. $\endgroup$ – Jerry M. Dec 7 '18 at 1:37

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.