# Time complexity in Big O notation for Harmonic series with first k terms missing

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.

• 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)$.] May 8 '13 at 1:15
• 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. May 8 '13 at 1:24
• You're losing some information when you simplify log(n/k) to O(log n). What if k = n/2? May 8 '13 at 1:41
• 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. May 8 '13 at 2:39

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