Big-Ohhhh!

Problem: Let $f : \mathbb{Z_{\geq 0}} \mapsto \mathbb{Z_{\geq 0}}$ be a non-decreasing function satisfying the inequality

$$f(n) \leq \frac{2}{n - 1} \left(n^2 + \sum^{n - 1}_{i = 1}f(i)\right)$$

Prove that $f(n) = O(n\log n)$.

Solution: Notice that $\frac{1}{n - 1} \dot \sum^{n - 1}_{i = 1}f(i)$ is the average value of $f$ over the interval $[1, n - 1]$. This suggests expanding the inequality is a good idea because we can simplify our expression.

$$f(n) \leq \frac{2n^2}{n - 1} + 2f(j) $$

Where $f(j) > \frac{1}{n - 1}\sum^{n - 1}_{i = 1}f(i)$  for the minimum $j$. Note that $\frac{2n^2}{n - 1}$ is $O(n)$ so

$$f(n) \leq O(n) + 2f(j)$$

What happens if we recursively apply the process we have just applied for $f(n)$, to $f(j)$? And how many times do we apply this process in the worst case so that $f(j) = f(1)$?

At worst we apply this process $O(\log n)$ times. Therefore, following through with recursion we are left with

$$f(n) \leq \underbrace{O(n) + O(n) + ... + O(n)}_{O(\log n) \text{ times}} + 2^{O(\log n)}f(1) = O(n \log n) + O(n)f(1) = O(n \log n)$$

I came across this problem in a past paper for one of my algorithms course and enjoyed the process of solving it. It felt like a real thinking questions which you couldn't prepare for that much.