Calculating time complexity of two interdependent nested for loops

Question

Consider the following code segment :

for (int i = 1; i <= n; i++ ) {
    for (int j = 1; j <= 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) &= \frac{n}{1} + \frac{n}{2} + \frac{n}{3} + \cdots + \frac{n}{n}\\ \\ &= n \left( 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} \right) \\\\ &= 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) $?

Answer 1

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 & = \ln n + \gamma + r(n) \\ r(n) & \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)$

Answer 2

Since you are only interested in the time complexity and can ignore a constant factor of two: Replace

1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/9 + 1/10 ...

with

1 + 1/2 + 1/4 + 1/4 + 1/8 + 1/8 + 1/8 + 1/8 + 1/16 + 1/16 ... 

for a lower bound, and with

1 + 1/2 + 1/2 + 1/2 + 1/4 + 1/4 + 1/4 + 1/4 + 1/8 + 1/8 ...

for an upper bound. Then add the 3rd and 4th term, the 5th to 8th term, the 9th to 16th term and so on.

Not that knowing the sum of harmonic numbers isn't a good thing to know, but having a good strategy helps you in cases where an exact formula isn't available.

Answer 3

The $n$th harmonic number is asymptotically $\ln n + \gamma + O\left(\frac{1}{n} \right)$, with $\ln n$ being the natural logarithm and $\gamma $ the Euler Constant. You can find all on Wikipedia's entry on the harmonic number.