Calculating time complexity of two interdependent nested for loops Consider the following code segment :

for (int i = 1; i &lt;= n; i++ ) {
    for (int j = 1; j &lt;= n; j = j + i ) {
          printf("Hi");
    }
}


Here, the outer loop will execute $ n $ times, but the execution of inner loop depends upon the value of $ i $.  


When $ i = 1 $ inner loop will execute $ n $ times.
When $ i = 2 $ inner loop will execute $ \frac{n}{2} $ times.
When $ i = 3 $ inner loop will execute $ \frac{n}{3} $ times.
$ \vdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \vdots  $
When $ i = n $ inner loop will execute $ 1 $ time  


So complexity will be given by
$$
 \begin{align}
  T(n) &amp;= \frac{n}{1} + \frac{n}{2} + \frac{n}{3} + \cdots + \frac{n}{n}\\
\\
       &amp;= n \left( 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} \right) \\\\
       &amp;= n \sum_{k = 1}^{n} { \frac{1}{k} }
 \end {align}
 $$
I am not able to solve $ \sum_{k=1}^{n} \frac{1}{k} $. Upon searching I found that it is the $ n^{th} $ Harmonic number ( $ H_n $), but couldn't find any closed formula for it. How can I proceed further to calculate $ T(n) $?
The $n^{th}$ harmonic number can be approximated by the integral $\int_1^n \frac{1}{x} \mathrm{d}x$.

\begin{align}
H_n \approx \int_1^n \frac{1}{x} \mathrm{d}x = \left[ \ln x \right]_1^n = \ln n - \ln 1 = \ln n
\end{align}

The limit of $H_n - \ln n$ is $\gamma \approx 0.577$, which is the Euler-Mascheroni constant.

Therefore, we get
\begin{align}
H_n &amp; = \ln n + \gamma + r(n) \\
r(n) &amp; \in \mathcal{O}\left(\frac{1}{n}\right)
\end{align}

Since $H_n - \ln n$ is not exactly $\gamma$, we need some remainder $r(n)$, whose limit is $0$.

So we get $T(n) = n \ H_n = n\ln n + n\gamma + n \ r(n) \in \mathcal{O}(n \log n)$