1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – gnasher729
    Commented Sep 19, 2023 at 6:08

3 Answers 3

0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – joeren1020
    Commented Nov 21, 2022 at 19:32
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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