I'm deep diving algorithms just to get better and was wondering if my assumption that the following algorithm has a time complexity of O(n^2) given the following input of [3, 5, -4, 8, 11, 1, -1, 6] and the targetSum input at: 10. I understand that the single iteration through the array has a time complexity of O(n) but I'm wondering if that if statement there makes the entire algorithm O(n^2) as I stated. Just looking for general discussion! Thanks!
def twoNumberSum(array,targetSum):
for x in array:
num = targetSum - x
if num in array and num != x:
return [x,num]
return []
Yes, for that input it's O(n^2). You can improve by converting the list into a set, The operation n in my_set has complexity O(1) so your code would be optimized to O(n) complexity.