educative.io

Brute force 2 pointer is O(N^2) with constant space isn't it?

Courses
,
#1

Can someone please explain why the brute force approach is inefficient, i.e., O(N^2) 2 pointer approach like bubble sort etc

def find_subarrays(arr, target):
    result = []
    if not arr:
        return result
    for left in range(len(arr)):
        product = arr[left]
        right = left
        while product < target:
            result.append(arr[left:right+1])
            right += 1
            if right >= len(arr):
                break
            product *= arr[right]
    return result
#2

array slicing is not constant time it is probably O(k) , can anyone confirm?

1 Like
#3

@simran is correct. Slicing is O(K) [where K is the size of the slice] so the runtime here is O(N^2 * K) but K is simplified to N even if technically, in most cases, it a sub N value, but its because it is a derived from N [N minus some constant less than N]. So the runtime is simplified to O(N^3)