Back to course home
0% completed
Vote For New Content
Possible Error in the time complexity
Giovanni Ruiz
Oct 16, 2023
I believe the time complexity of the problem would be N^2, instead of N^3 as pointed out in the solution as we go through the outer loop (N), and go through the inner while loop (N) once again, making it (N^2)
0
0
Comments
Comments
Bruno Ely2 years ago
The O(N^3) complexity is for the solution to the problem under "Similar Problems" (not the main problem), which requires enumerating every single triplet rather than counting how many there are. For that problem, the inner loop can take up to O(N^2) time in the worst ca...