Solution Review: Problem Challenge 2 - Grokking the Coding Interview: Patterns for Coding Questions, here the time complexity of proposed solution is mentioned as O(nlogn). In the wortst case the nested loop will run i+1, i+2, i+3… n, hence the nested loop will have time complexity of O(n). Time complexity of first loop is n. So, the time complexity of this program should be O(n^2), no? Please correct me if I am wrong.
Hi, the time complexity is O(N * LogN) because the sorting algorithm since we are sorting the jobs in accordance with their start times.