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.<p>(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))<p>EDIT: I assumed the first solution would compare each character to the characters visited so far, i.e.<p><pre><code> for i in [0..N]
for j in [0..i]
if arr[i] == arr[j] return arr[i]
</code></pre>
Maybe it's<p><pre><code> for i in [0..N]
for j in [0..N]
if arr[i] == arr[j] && i != j
return arr[i]
</code></pre>
That would make it O(KN). Or O(N) if we treat the size of the alphabet as fixed.