Posting a new thread as reply to the question prompt:
I’m walking through this example with the worst case [1,1,1,1,1,1,1,1,1,1,1,1] and I feel like this is O(N^3)? (target = 4) The inner inner loop is guaranteed run for the full range regardless of sort. Is O(N∗logN+N^2) correct?
Hi @Bao_Nguyen,
Yes, it is O(N^3). We’ve corrected this. Since we will be saving all such triplets, we will need O(N^3); if we were only counting such triplets we can do this in O(N^2) though.
For Loop runs O(N) times
While loop runs O(N-1) times
List runs O(N-2) times
O(N(N-1)(N-2)) = O(N^3)