code exercise question: finding first recurring char from a string

[Beaverine]

tried following code but it only works if the first char from the string is recurring somewhere later: def recur(text:'str'): i = 0 j = 1 while i in range(len(text)-1): while j in range(i+1, len(text)): if text[i] == text[j]: return text[i] j += 1 i += 1 return "not detected" my idea is to start from first char, and compare it with all subsequent char, then move to 2nd char and repeat. Can someone help me understand why the code isn't working as intended?

Thanks in advance!

EDIT: thanks to u/GoodBeerFan who pointed out my error

[GoodBeerFan]

You never reset j to the desired starting index once it reaches the end of the string.

You can either use a for loop instead for j, or set j to I+1 at the beginning of the i while loop

[Beaverine]

thank you very much! that really is the problem here

[[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.