0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ In fact, it's quite a bit more complicated than I thought. To see the problem here, take a look at this related question. $\endgroup$ – Rick Decker Nov 8 '16 at 21:25
  • $\begingroup$ Ok, that's very subtle...., but what happen if we drop the Big O in this recurrence? $\endgroup$ – Wyvern666 Nov 8 '16 at 21:34
  • 1
    $\begingroup$ I don't understand the setup. A form with one variable $n$ and $T(n)$ on the left-hand side would be more useful. $\endgroup$ – Raphael Nov 8 '16 at 23:06
  • $\begingroup$ 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! $\endgroup$ – Raphael Nov 8 '16 at 23:06
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Wyvern666 Nov 9 '16 at 1:00
  • $\begingroup$ 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. $\endgroup$ – Lee Nov 9 '16 at 2:17
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.