[asdginioubnou]

Both solutions are O(1). The alphabet is finite. Let's say there are M different characters in the alphabet and N different characters in the string. If there is a duplicate, it is guaranteed to occur within the first M + 1 characters of the string by the pigeonhole principle. As N grows without bound, the number of characters that needs to be checked reaches a limit.

(I guess, most precisely, we should define K to be min(M + 1, N). Then the first solution is O(K^2) and the second solution is O(K))

EDIT: I assumed the first solution would compare each character to the characters visited so far, i.e.

    for i in [0..N]
        for j in [0..i]
           if arr[i] == arr[j] return arr[i]

Maybe it's

    for i in [0..N]
        for j in [0..N]
           if arr[i] == arr[j] && i != j
               return arr[i]

That would make it O(KN). Or O(N) if we treat the size of the alphabet as fixed.

[asdginioubnou]

>Let's say there are M different characters in the alphabet and N different characters in the string.

I mean "N characters in the string", i.e. the string is length N. There won't be N different characters.

[v_g]

Interesting point. However, Alphabet is probably not the best example, Unicode perhaps? The upper bound in Unicode is ~ 1.1 Million, but still fixed

[asdginioubnou]

That doesn't make a difference asymptotically, though it obviously makes a big difference in practice.