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 &lt; k &lt; 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.
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). $$