CODEWITHSUNDEEP
algorithmgo
Daniel Wilk
Daniel Wilk

Reputation: 21

Two number sum algorithm

Time complexity of an algorithm below is O(log(n)), but I'm just curious what is time complexity of the for loop?

func TwoNumberSum(array[] int, target int)[] int {
    sort.Ints(array)
    left, right: = 0, len(array) - 1
    for left < right && left >= 0 && right < len(array) {
        if array[left] + array[right] == target {
            return [] int {
                array[left], array[right]
            }
        } else if array[left] + array[right] < target {
            left += 1
        } else {
            right -= 1
        }
    }
    return [] int {}
}

Upvotes: 2

Views: 81

Answers (1)

Abhinav Mathur
Abhinav Mathur

Reputation: 8101

Time complexity of an algorithm below is O(log(n))

The claim is incorrect. For input = [1,2,3,4,5] and target = 9, left will traverse the entire array. The complexity of the for loop, and for the entire algorithm, is O(n).

Edit: I just noticed the extra sort() call. Sorting will make the algorithm's complexity O(nlogn).

Upvotes: 3

Related Questions