Algorithmic complexity of naive code for processing all consecutive subsequences of a list: n^2 or n^3?
algorithm, big-o, java, time-complexity
Solution
You can proceed methodically, using Sigma Notation, to obtain the order of growth complexity:
Problem
I'm studying for a test and found this question: I can't really determine the complexity, I figured it's either O(n2) or O(n3) and I'm leaning towards O(n3). Can someone tell me what it is and why? My idea that it's O(n2) is because in the `j` loop, `j = i` which gives a triangle shape, and then the `k` loop goes from `i + 1` to `j`, which I think is the other half of the triangle. ``` public static int what(int[] arr) { int m = arr[0]; for (int i=0; i<arr.length; i++) { for (int j=i; j<arr.length;j++) { int s = arr[i]; for (int k=i+1; k<=j; k++) s += arr[k]; if (s > m) m = s; } } return m; } ``` Also if you can tell me what it does? I figured it returns the addition of positive integers or the biggest integer in the array. But for arrays like `{99, -3, 0, 1}` it returns `99`, which I think is because it's buggy. If not than I have no Idea what it does: ``` {99, 1} => returns 100 {-1, -2, -3} => return -1 {-1, 5, -2} => returns 5 {99, -3, 0, 1} => returns 99 ??? ```