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 = nln n + ngamma + n r(n) in mathcal{O}(n log n)$
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/22823
