2
$\begingroup$

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)
}
$\endgroup$

3 Answers 3

3
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

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

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