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 i

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.