2
$\begingroup$

Firstly, let's suppose there exists an algorithm where $i$ iterates from $1$ to $n$, spending $\frac{n^2}{i}$ time in each iteration.

Thanks to the well known $O(\log n)$ upper bound for the Harmonic series, the big $O$ notation of this algorithm comes to $O(n^2 \log n)$.

Now the actual algorithm that I am working on iterates from $k$ to $n$, where $1 < k < n$, spending $\frac{n^2}{k}$ in the first iteration, then $\frac{n^2}{k+1}$, $\frac{n^2}{k+2}$, $\frac{n^2}{k+3}$, and so on.

I've been trying to deduce the upper bound of this new algorithm, but I keep getting the same $O(n^2 \log n)$ time bound, which to me, is counter intuitive and a bit paradoxical, especially considering that the first terms of the harmonic series are the bigger and more significant terms. The time bound that I was actually expecting to get was $O(\frac{n^2}{k} \cdot \log n)$.

Could anyone please be able to shed some light onto this?

Thanks in advance for any help.

$\endgroup$
4
  • 2
    $\begingroup$ This is not a research-level question in theoretical computer science; please see the faq for more details. [Hint: $H_n \approx \ln n$, so $H_n - H_k \approx \ln(n/k)$.] $\endgroup$
    – JeffE
    May 8 '13 at 1:15
  • $\begingroup$ O(n^2 * log(n/k)) = O(n^2logn - n^2logk) = O(n^2logn), so basically you've just confirmed what I originally deduced. I was hoping that there would be something non-obvious hidden in there somewhere. Thanks for your comment on this entry level question. $\endgroup$
    – wookie919
    May 8 '13 at 1:24
  • $\begingroup$ You're losing some information when you simplify log(n/k) to O(log n). What if k = n/2? $\endgroup$
    – JeffE
    May 8 '13 at 1:41
  • $\begingroup$ Well, yes. I guess I didn't specify that k = n^t for some t < 1. log(n^0.0000001) = 0.0000001(logn) = O(logn). The big O notation really irritates me sometimes. $\endgroup$
    – wookie919
    May 8 '13 at 2:39
2
$\begingroup$

We can estimate your sum using an integral: $$ \int_k^{n+1} \frac{dx}{x} \leq \sum_{i=k}^n \frac{1}{i} \leq \int_{k-1}^n \frac{dx}{x}. $$ Evaluating the integrals, we obtain $$ \log \frac{n+1}{k} \leq \sum_{i=k}^n \frac{1}{i} \leq \log \frac{n}{k-1}. $$ We can conclude that for $k \geq 2$, $$ \sum_{i=k}^n \frac{1}{i} = \log \frac{n}{k} \pm O(1). $$

$\endgroup$

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.