Upper bounding this expression

Question

I need to prove that the following expression is $\mathcal O(n \log n)$ with the substitution method: $$ T(n) \leq 3\log n + n + \frac{6}{n}\sum^{n - \frac{\log n}{3}}_{i=\frac{\log n}{3}} T(i)$$

This is my attempt, assumming $T(n) \leq c n \log n$: \begin{align*} T(n) &\leq 3\log n + n + \frac{6c}{n}\int^{n - \frac{\log n}{3}}_{\frac{\log n}{3}} x\log x dx\\ &= 3\log n + n + \frac{6c}{n}\left[ \frac{x^2 \log x}{2} - \frac{x^2}{4}\right]\bigg|^{n - \frac{\log n}{3}}_{\frac{\log n}{3}}\\ &= 3\log n + n +\frac{6c}{n}\left[ \frac{n^2}{2}\log \left(n-\frac{\log n}{3}\right)-\frac{n}{3}\log n \log \left(n - \frac{\log n}{3}\right) + \frac{\log^2 n \log(n-\frac{\log n}{3})}{18}-\frac{n^2}{4}+\frac{n\log n}{6}-\frac{\log^2 n\log (\frac{\log n}{3})}{18}\right]\\ &=3\log n + n + 3cn \log(n - \frac{\log n}{3})-2c \log n \log(n - \frac{\log n}{3})+\frac{c\log^2n \log(n - \frac{\log n}{3})}{3n} - \frac{3nc}{2}+c\log n-\frac{c\log^2 n \log (\frac{\log n}{3})}{3n}. \end{align*}

What else can I do?

Answer 1

Consider the right hand side. Use $\log(n-\frac{\log n}{3})\leq \log n,$ to simplify the $\log n$ terms. Clearly the second term is at most $3 c n \log n.$

Since all other terms are of lower order (since they are powers of $\log n$ or smaller (such as being divided by $n$ for example)) the right hand side is $\leq 3c n\log n.$

For any positive constant $c$, the LHS for which you guessed $c n \log n$ is smaller than $3c n \log n$ so you can apply the substitution method and you are done.

Answer 2

Clearly,

$$ \frac{6}{n}\sum^{n - \frac{\log n}{3}}_{i=\frac{\log n}{3}} T(i)<\frac{6}{n}\sum^{n}_{i=1} T(i)$$

and using your integral, this is smaller than

$$\frac6n\frac{n^2\log n}2=3n\log n.$$

Now,

$$n\log n<3\log n+n+3n\log n.$$

Answer 3

If you have T(n) <= c n log n for all n < N, then you show that T(N) <= 3 c N log N. That’s just not good enough.

It seems that T(n) for large n is quite exactly 6 times the average of all smaller values. T(n) = c * n^5 would do that. And c * n^4 wouldn’t. Integral of n^5 is n^6/6, times 6/n is n^5 again.

I’d say T(n) / n^5 converges to some constant c > 0. Write a program to calculate the first 2^30 values of T(n) and print T(n) / n^5 when n is a power of two. The calculation takes linear time and O(log n) space.