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?
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)