I'm trying to determine a big O notation for the following code snippet - just wanted to confirm if this method makes sense?
1 public static int func3(int[ ] arr) {
2 int n = arr.length, total = 0;
3 for (int j=0; j < n; j++) // loop from 0 to n-1
4 for (int k=0; k <= j; k++) // loop from 0 to j
5 total += arr[j];
6 return total;
7 }
If I let lines 2 and 6 be $a$ they are evaluated 1 times,
line 3 be $b$ which is evaluated $n+1$ times
line 4 be $c$ which is evaluated $\sum_{i=0}^{n-1}(i+2)$ times
line 5 be $d$ which is evaluated $\sum_{i=0}^{n-1}(i+1)$ times
I end up getting: $$a+(n+1)b + \sum_{i=0}^{n-1}[(i+2)c+(i+1)d]$$ $$a+(n+1)b + \sum_{i=0}^{n-1}[2c+d+i(c+d)]$$ $$a+(n+1)b + 2cn + dn + (c+d) \sum_{i=0}^{n-1}[i]$$ $$a+(n+1)b + 2cn + dn + (c+d)\cdot \frac{n}{2}\cdot(n-1)$$ $$a+(n+1)b + 2cn + dn + (c+d)\cdot \frac{n^2-n}{2}$$ $$2a+2bn+2b + 4cn + 2dn + cn^2 -cn+dn^2 -dn$$ $$n^2(c+d)+n(2b+3c+d)+2a+2b$$ Therefore a big-Oh characterization,in terms of n, of the running time is $O(n^2)$