# Upper bounding this expression

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?

• Write a quick program calculating the first billion values and check if what you try to prove looks plausible. Looks like T(n) is about 6 times the average of all smaller values. N log n would be smaller. Sep 19 at 6:08

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.

• I think that by the substitution method I have to bound the given expression by $cn \log n$. If I already have $3cn \log n$ on the LHS then the inequality wouldn't be possible. Nov 21, 2022 at 19:32

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

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.