[Solved]: Calculating time complexity of two interdependent nested for loops

Problem Detail: 

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

Asked By : nangal.vivek

Answered By : Gaste

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22823