The final Complexity Analysis doesn't make sense "The two main loops are in the order of N each, leading to O(N^2)..." That's incorrect, the first loop is O(N) , but the second is O(N^2) - so that's why the resulting complexity is O(N^2). (summing O(N) and O(N) still gives O(N), not O(N^2)).

"This particular implementation also has O(N^2)" - huh? I'm thinking this is a redundant sentence.

luke-guyton• 3 years agoThe final Complexity Analysis doesn't make sense "The two main loops are in the order of N each, leading to O(N^2)..."

That's incorrect, the first loop is O(N) , but the second is O(N^2) - so that's why the resulting complexity is O(N^2). (summing O(N) and O(N) still gives O(N), not O(N^2)).

"This particular implementation also has O(N^2)" - huh? I'm thinking this is a redundant sentence.

"this can be optimized down to O(N)" - how?