0
$\begingroup$

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; } 
  • 0
    For some basic information about writing math at this site see e.g. [here](http://meta.math.stackexchange.com/questions/5020/), [here](http://meta.stackexchange.com/a/70559/155238), [here](http://meta.math.stackexchange.com/questions/1773/) and [here](http://math.stackexchange.com/editing-help#latex).2012-12-04

1 Answers 1

2

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