On pramp.com I was given this interview question:

Given a package with a weight limit limit and an array arr of item weights, implement a function getIndicesOfItemWeights that finds two items whose sum of weights equals the weight limit limit. Your function should return a pair [i, j] of the indices of the item weights, ordered such that i > j. If such a pair doesn’t exist, return an empty array.

Analyze the time and space complexities of your solution.

Example:

input: arr = [4, 6, 10, 15, 16], lim = 21

output: [3, 1] # since these are the indices of the # weights 6 and 15 whose sum equals to 21

Initially I was thinking of a solution which iterated over the the array, then an inner loop to iterate over the remaining array to check if the compliment exists (limit - elementA = elementB).

Here's my code:

def get_indices_of_item_weights(arr, limit):    
    for idx, i in enumerate(arr):
        diff = limit - i          
        if diff in arr[idx+1:]:   # constant lookup
            for idx2, j in enumerate(arr[idx+1:]):
                if j == diff:
                    return [idx+idx2+1, idx]
    return []

The website explained that a solution like this is still O(N^2) time complexity. But isn't it diminishing in time complexity since the remaining array becomes smaller? i.e. O(log N).

Can someone help explain why that approach is not O(log N)?