Big-Oh of recursive function

Question

Can someone please explain to me why this function runs in O($n^2$) rather than O($n^3$). I feel like since that for loop runs in O($n^2$) and f() is recursively called around n times, that it should end up being $n\cdot n^2$ for an overall O($n^3$).

f(n) {
    if (n == 0) {
        return 0
    }

    int result = 0
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            result += j

        }
    }
    return f(n/2) + result + f(n/2)
}

Answer 1

The reason is easier to see when you figure the big-$\mathrm O$ of the loop and the recursion (last line) separately and then add them. The loop takes $\mathrm O(n^2)$ time, and the recursive part takes twice the time of $f(n/2)$.

So we get $$\mathrm{time} (f(n))=\mathrm O(n^2 + 2\mathrm{time}(f(n/2)))\tag a$$

and we can simplify this by noticing that this will form a geometric sequence.

$$ = \mathrm O(n^2+2\left(n/2\right)^2 + 4\mathrm{time}(f(n/4)))\tag b$$ $$ = \mathrm O(n^2 + 2(n/2)^2 + 4(n/4)^2 + 8\mathrm{time}(f(n/8)))\tag c$$ $$= \mathrm O\left(\sum_{i=0}^{\inf} \frac{n^2}{2^{i}}\right)\tag d$$ $$= \mathrm O\left( n^2\sum_{i=0}^{\inf}\left(\frac{1}{2^{i}}\right)\right)\tag e$$

$\sum_{i=0}^{\inf}\left(\frac{1}{2^{i}}\right)$ on line $\mathrm (e)$ converges to a nonzero value that is not dependant on $n$ (specifically, $2$), so it can be removed from the $\mathrm {O}()$, to give just $\mathrm O(n^2)$

---

Note that this way of solving (leaving constant factors and ignoring the base case of recursion) will not work for all problems.

For example what if the inner loop had time complexity $\mathrm O(n)$? $$\mathrm{time}(f(n)) = \mathrm O(n + 2\mathrm{time}f(n/2)) = \mathrm O(n + 2\frac{n}2+4\mathrm{time}f(n/4)) = ...$$ which would give $\mathrm O\left( n^2\sum_{i=0}^{\inf}1\right)$, which is obviously not correct because it diverges.
However, if we ingore the constant factor of 2, we get $$\mathrm{time}(f(n)) = \mathrm O(n + \mathrm{time}f(n/2)) = \mathrm O(n + \frac{n}2+\mathrm{time}f(n/4)) = ...$$ which gives $\mathrm O\left( n^2\sum_{i=0}^{\inf}\frac1{2^n}\right)$, which converges to $2$

-- End note

Answer 2

Let n = 1024 and write down the number of additions in each call. With concrete numbers. See how the numbers develop. Then see if the numbers agree with your hypothesis. Since they don't, fix your hypothesis.

Answer 3

Suppose the time complexity of running $f(n)$ is denoted by $T(n)$. As the computing the result takes $\sum_{i=0}^{n-1}\sum_{j=0}^{i-1}1 = \sum_{i=0}^{n-1} i = \frac{(n-1)n}{2} = \Theta(n^2)$, we can write:

$$ T(n) = 2T(\frac{n}{2})+ \Theta(n^2) $$

Now, using the master theorem, as $n^{\log_2(2)} = n$ and $\log(n) = o (\frac{n^2}{n})= o(n)$, we can say $T(n) = \Theta(n^2)$.