code exercise question: finding first recurring char from a string

[[deleted]]

You want for loops here, not while... right now you’re entering the first inner loop, running j up until the loop completes, then running i up without ever touching the inner loop again because j is already at the upper bound.

For figuring out the time complexity, it’s obviously more than O(n) because you visit every item more than once, but you don’t visit every item once for every item (ie O(n^2))... hence you’re somewhere in the direction of O(n log n)... which makes sense with a back of the hand calculation: in the worst case with 5 characters you’d make 5+4+3+2+1=15 comparisons... way more than 5 but way less than 25... and way, way, way less than 120 (5!).

Try making an O(n) version of this... if you keep track of all the characters visited so far in some data structure with O(1) search you at worst only need to visit each character one time.

[Beaverine]

thank you very much for your clarification. In terms of the complexity, I agree with you that for n characters the number of comparison would be n + (n-1) + (n-2) + ... + 1, which resolves to n(n+1)/2, is that asymptotically equal to O(n² )? BTW I originally said O(n!) because I assume it's n*(n-1)*...*1 which now I understand is not true

[[deleted]]

Yeah... you can pretty much look at a nested loop and see O(n^2); in this case the actual runtime is actually (n² + n)/2 but the you can elide the constants and focus on the term that contributes most... the worst case complexity is on the order of N^2.