educative.io

Educative

Time complexity of searchPair() function

in notebook it says - Time complexity ##

I feel confused , if final complexity is O(N^2) then searchPair() function should be O(N^2) instead of O(N), right?

Hi @Wenny_H

The time complexity of the searchPair() function is O(N). As this function is called for every number in the input array, the total time complexity of these calls turns out to be O(N^2). Therefore,

Time complexity of the searchTriplets() function = Time complexity of the sort() function + N * (Time complexity of the searchPair() function)
Time complexity of the searchTriplets() function = O(N*logN) + N*O(N) = O(N*logN) + O(N^2) = O(N^2)