The time complexity stated for solution 2 is O(nlogn). I believe the time complexity should be O(n) as there is only one while loop for iteration. Am I missing something?
Course: Coderust: Hacking the Coding Interview - Learn Interactively
Lesson: Find Pair With Given Sum in an Array
Hello @Muhammad_Asad, thank you for reaching out. Let’s look at how we have calculated the time complexity of O(n log n).
To sort the nums vector, the sorting process usually takes O(n log n) time, where ‘n’ represents the number of elements in the nums vector.
The main loop, which utilizes a two-pointer approach, continues running as i is less than j. Here, i and j serve as markers for the end and high end of the vector. In a worst-case scenario, both i and j may traverse the vector once, resulting in O(n) iterations.
Within the loop, calculating the sum of two elements and comparing it to the target value is an operation that takes time.
The sorting step with a complexity of O(n log n) is the significant factor affecting time complexity. The two-pointer approach and element comparisons have a complexity of O(n) in worst-case scenarios. As sorting dominates in terms of time complexity, we can conclude that the overall code has a time complexity of O(n log n).
I hope this will help.
Happy learning
