Back to course home
0% completed
Vote For New Content
Time Complexity
Jessica Liang
Jul 19, 2023
Why is the solution's time complexity O(n^2)?
If sorting the array takes O(nlogn) time and searchPair() takes O(n) time, why does searchTriplets() take O(n^2) time? I thought the time complexity would have been O(nlogn + n) ~= O(nlogn).
0
0
Comments
Comments
E
Ejike Nwude2 years ago
The time complexity should be O(n^2). This is because for every element in the searchTriplets() for loop, searchPair() is called and it contains a while loop that iterates while left < right. This code is equivalent to a nested loop which in the worst case is O(n^2). Th...
Design Gurus2 years ago
There are two problems discussed in the chapter.
- The first problem is to return the count of triplets which takes $O(N^2)$.
- The second problem (under "Similar Problems") returns the list of such triplets that takes $O(N^3)$.