# Find an upper bound for a Linear Recurrence

Im having a hard time trying to figure out how to find an upper bound to the following recurrence:

$T(N)=T(N-1)+\mathcal{O}(n)$

where i know initially $N=\lfloor\tfrac{n}{logn}\rfloor$

I believe it can be solved as a linear recurrence, but i don't know how to put $n$ in terms of $N$.

• In fact, it's quite a bit more complicated than I thought. To see the problem here, take a look at this related question. – Rick Decker Nov 8 '16 at 21:25
• Ok, that's very subtle...., but what happen if we drop the Big O in this recurrence? – Wyvern666 Nov 8 '16 at 21:34
• I don't understand the setup. A form with one variable $n$ and $T(n)$ on the left-hand side would be more useful. – Raphael Nov 8 '16 at 23:06
• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – Raphael Nov 8 '16 at 23:06

You say that $N=\lfloor\tfrac{n}{logn}\rfloor$. But since you have a linear recurrence in N, not n, you really want n as a function of N.

We have $n ≈ N \log n$.

You substitute this for n and get $n ≈ N \log (N \log n) = N \log N + N \log \log n$.

$\log \log n$ is small compared to $\log N$, so we ignore it and get $T(N)=T(N-1)+\mathcal{O}(N \log N)$

We get $T(N)$ by summing $\mathcal{O}(k \log k)$ for k = 1 to N, which will be $\mathcal{O}(N^2 \log N)$.

• Mmmm, interesting. I didn't tried your second step, and got stuck easily. I was expecting $T$ to be $\mathcal{O}(n \log \log n)$ wich is more thight. Maybe i need to reconsider the $\mathcal{O}(n)$ term, because i know it get smaller on every recursive call. – Wyvern666 Nov 9 '16 at 1:00
• If $n = N \log n$, then $\log n = \log(N \log n) = \log N + \log\log n$, therefore $N \log n = N\log N + N \log\log n$. Unfortunately, it turns out that this approximation isn't actually very tight. For example, $n(z)$ is actually contractive since $\lim_{N \to \infty} \log\log n(N) = -N\log N + 1$ asymptotically, so $n(N)$ eventually tends towards 1. – Lee Nov 9 '16 at 2:17

Finding a good analytic characterization of $n(N)$ is tricky. Let's first consider the relaxation where $N = \frac{n}{\log n}$ without the flooring restriction. Here's a somewhat nonintuitive approximation: let $m(z) = 1 + \frac{1}{z}$, let's see how $\frac{m(z)}{\log m(z)}$ behaves as a function of $z$:

$$\begin{array}{ccc} z = 1 & 10 & 100 & 1000 & 10000 \\ 2.88\dots & 11.54\dots & 101.50\dots & 1001.50\dots & 10001.50\dots \end{array}$$

Asymptotically, this seems to give a good approximation of $n(N)$.

In fact, the Laurent series for $n(z)$ around $z = \infty$ is $$n(z) = 1 + \frac{1}{z} + \frac{3}{2z^2} + O(z^{-3})$$ and a second order truncation seems to be a good approximation for nearly all positive integers (even if we add in the flooring restriction, it is the correct answer for $N \ge 2$). Therefore, we're looking for the telescoping series $$T(N) = \sum_{1 \le k \le N} n(k) = N + H(N) + \frac{\pi^2}{4} - \frac{3}{2} \cdot \frac{3 + 2N}{2(N+1)^2} + O(N^{-2})$$ where $H(N) = \sum_k^N k^{-1} = O(\log N)$ is the harmonic series. This then shows that a tighter bound for your series is just $\Theta(N)$ asymptotically.