What is the time complexity of this brute force solution?


  • 0
    S

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

  • 1
    V

    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.


  • 0
    J

    Upper bound Θ(n^3)


Log in to reply
 

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