Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How would I go about calculating the Big O of this function?

I am told the answer is $O(n^{12})$ but cannot determine why it is not $O(n^9)$.

public int frag (int n) {
    int sum = 0;
    for (int i = 0; i < n * n * n; i++)
        for(int j = i * i * i; j > 0; j--)
            sum = sum + 2;
    return sum;
share|cite|improve this question
For some basic information about writing math at this site see e.g. here, here, here and here. – Julian Kuelshammer Dec 4 '12 at 23:48

The inner loop executes $i^3$ times, adding $2i^3$ to $sum$. So the outer loop gives $sum=\sum_{i=0}^{n^3-1} 2i^3=2\left(\frac {(n^3-1)n^3}2\right)^2$ from Faulhaber's formula

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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