# What is the time complexity of this brute force solution?

• I'm solving this problem. What is the longest increasing subarray (not subsequence. This means all elements in the subarray need to be contiguous in the array)

For example in array [1, 2, 3, 4, 5], [2, 3, 4] is a subarray but [1, 3, 4, 5] is not.

My brute force solution is below. I don't think it's O(n^2) bc each operation is taking O(j - i) time. What's the time complexity and can someone write a proof for it?

``````public int longestIncreasingSubarrayBruteForce(int[] array) {
int longestLength = 0;
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length; j++) {
longestLength = Math.max(getSubarrayLength(array, i, j), longestLength);
}
}

return longestLength;
}

private int getSubarrayLength(int[] array, int start, int end) {
int subarray = 1;
for (int i = start + 1; i <= end; i++) {
if (array[i] > array[i - 1]) {
subarray++;
}
else {
// Not subarray
return 0;
}
}
return subarray;
}``````

• It is at least `N^2` because the operation is being run that many times. Now that is assuming the operation itself is constant time. With big O notation, we must look at the worst case and for the `getSubarrayLength` operation, the worst case is `start = 0` and `end = n`, so this runs in linear time.

Therefore, for all `N^2` iterations, there is an operation that runs in linear time. This brute force solution will then run in `N^3` time.

• Upper bound `Θ(n^3)`

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.