Solve the recurrence:
| |
AN=1+2NN∑j=1Aj−1 for N>0NAN=N+2N∑j=1Aj−1(N−1)AN−1=(N−1)+2N−1∑j=1Aj−1for N−1 instead of NNAN−(N−1)AN−1=1+2AN−1subtract the last two equationsNAN=(N+1)AN−1+1note it's now linear time, not quadratic!ANN+1=AN−1N+1N(N+1)divide both sides by N(N+1)ANN+1=A12+12⋅3+⋯+1N(N+1)telescope=11⋅2+12⋅3+⋯+1N(N+1)note A1=1, assuming A0=0AN=(N+1)N∑k=11k(k+1)=(N+1)N∑k=1(1k−1k+1)partial fraction=(N+1)(1−1N+1)telescoping seriesAN=N◻ |
Alternatively, instead of using telescoping series,
| |
AN=(N+1)N∑k=1(1k−1k+1)AN∼NN∑k=1(1k−1k+1)f(x)∼g(x) meanslim |
By the definition of
Euler's constant,
| |
\begin{aligned}
\gamma &= \lim_{N \rightarrow \infty} \big( \sum_{k=1}^N \frac{1}{k} - \ln N \big) \\
\therefore \lim_{N \rightarrow \infty} \big( \sum_{k=1}^N \frac{1}{k} &= \ln N + \gamma \big) \\
\gamma &= 1 + \lim_{N \rightarrow \infty} \big( \sum_{k=2}^N \frac{1}{k} - \ln N \big) & \text{pull out the 1st term} \\
&= 1 + \lim_{N \rightarrow \infty} \big( \sum_{k=1}^{N-1} \frac{1}{k+1} - \ln N \big) & \text{re-index} \\
\lim_{N \rightarrow \infty} \big( \sum_{k=1}^{N-1} \frac{1}{k+1} &= \ln N + \gamma - 1 \big) \\
\therefore \lim_{N \rightarrow \infty} \big( \sum_{k=1}^{N} \frac{1}{k+1} &= \ln (N+1) + \gamma - 1 \big) & \text{for } N+1 \text{ instead of } N \\
\end{aligned}
|
Hence
| |
\begin{aligned}
A_N &\thicksim N \big(\sum_{k=1}^N \frac{1}{k} - \sum_{k=1}^N \frac{1}{k+1}\big) \\
A_N &\thicksim N \big[ \big(\ln N + \gamma\big) - \big(\ln (N+1) + \gamma - 1\big) \big] \\
A_N &\thicksim N \big(\ln N - \ln (N+1) + 1\big) \\
A_N &\thicksim N &\Box \\
\end{aligned}
|
Source:
Analysis of Algorithm
# posted by rot13(Unafba Pune) @ 9:27 AM
