Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

1 Answer 1

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|improve this answer

Your Answer

 
discard

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.