Time complexity calculation for my algorithm

Question

Given a string, find the first non-repeating character in it and return its index. If it doesn't exist, return -1. You may assume the string contain only lowercase letters.

I'm going to define a hash that tracks the occurrence of characters. Traverse the string from left to right, check if the current character is in the hash, continue if yes, otherwise in another loop traverse the rest of the string to see if the current character exists. Return the index if not and update the hash if it exists.

def firstUniqChar(s):

    track = {}
    for index, i in enumerate(s):
        if i in track:
            continue
        elif i in s[index+1:]: # For the last element, i in [] holds False
            track[i] = 1
            continue
        else:
            return index
    return -1

firstUniqChar('timecomplexity')

What's the time complexity (average and worst) of my algorithm?

Answer 1

As others have noted, your algorithm is O(n²) due to nested linear search. As discovered by @Antti, the OP's algorithm is linear and bound by O(kn) for k as the number of all possible lowercase letters.

My proposition for an O(n) solution:

from collections import OrderedDict

def first_unique_char(string):
    duplicated = OrderedDict()  # ordered dict of char to boolean indicating duplicate existence
    for s in string:
        duplicated[s] = s in duplicated

    for char, is_duplicate in duplicated.items():
        if not is_duplicate:
            return string.find(char)
    return -1

print(first_unique_char('timecomplexity'))  # 4

Answer 2

Your algorithm has time complexity of O(kn) where k is the number of unique characters in the string. If k is a constant then it is O(n). As the problem description clearly bounds the number of alternatives for elements ("assume lower-case (ASCII) letters"), thus k is constant and your algorithm runs in O(n) time on this problem. Even though n will grow to infinite, you will only make O(1) slices of the string and your algorithm will remain O(n). If you removed track, then it would be O(n²):

In [36]: s = 'abcdefghijklmnopqrstuvwxyz' * 10000

In [37]: %timeit firstUniqChar(s)
100 loops, best of 3: 18.2 ms per loop

In [38]: s = 'abcdefghijklmnopqrstuvwxyz' * 20000

In [37]: %timeit firstUniqChar(s)
10 loops, best of 3: 36.3 ms per loop

In [38]: s = 'timecomplexity' * 40000 + 'a'

In [39]: %timeit firstUniqChar(s)
10 loops, best of 3: 73.3 ms per loop

It pretty much holds there that the T(n) is still of O(n) complexity - it scales exactly linearly with number of characters in the string, even though this is the worst-case scenario for your algorithm - there is no single character that is be unique.

---

I will present a not-that efficient, but simple and smart method here; count the character histogram first with collections.Counter; then iterate over the characters finding the one

from collections import Counter
def first_uniq_char_ultra_smart(s):
    counts = Counter(s)
    for i, c in enumerate(s):
        if counts[c] == 1:
            return i

    return -1

first_uniq_char('timecomplexity')

This has time complexity of O(n); Counter counts the histogram in O(n) time and we need to enumerate the string again for O(n) characters. However in practice I believe my algorithm has low constants, because it uses a standard dictionary for Counter.

And lets make a very stupid brute-force algorithm. Since you can assume that the string contains only lower-case letters, then use that assumption:

import string
def first_uniq_char_very_stupid(s):
    indexes = []
    for c in string.ascii_lowercase:
        if s.count(c) == 1:
            indexes.append(s.find(c))

    # default=-1 is Python 3 only
    return min(indexes, default=-1)

Let's test my algorithm and some algorithms found in the other answers, on Python 3.5. I've chosen a case that is pathologically bad for my algorithm:

In [30]: s = 'timecomplexity' * 10000 + 'a'

In [31]: %timeit first_uniq_char_ultra_smart(s)
10 loops, best of 3: 35 ms per loop

In [32]: %timeit karin(s)
100 loops, best of 3: 11.7 ms per loop

In [33]: %timeit john(s)
100 loops, best of 3: 9.92 ms per loop

In [34]: %timeit nicholas(s)
100 loops, best of 3: 10.4 ms per loop

In [35]: %timeit first_uniq_char_very_stupid(s)
1000 loops, best of 3: 1.55 ms per loop

So, my stupid algorithm is the fastest, because it finds the a at the end and bails out. And my smart algorithm is slowest, One more reason for bad performance of my algorithm besides this being worst case is that OrderedDict is written in C on Python 3.5, and Counter is in Python.

---

Let's make a better test here:

In [60]: s = string.ascii_lowercase * 10000

In [61]: %timeit nicholas(s)
100 loops, best of 3: 18.3 ms per loop

In [62]: %timeit karin(s)
100 loops, best of 3: 19.6 ms per loop

In [63]: %timeit john(s)
100 loops, best of 3: 18.2 ms per loop

In [64]: %timeit first_uniq_char_very_stupid(s)
100 loops, best of 3: 2.89 ms per loop

So it appears that the "stupid" algorithm of mine isn't all that stupid at all, it exploits the speed of C while minimizing the number of iterations of Python code being run, and wins clearly in this problem.

Answer 3

Your algorithm is O(n²), because you have a "hidden" iteration over a slice of s inside the loop over s.

A faster algorithm would be:

def first_unique_character(s):
    good = {} # char:idx
    bad = set() # char
    for index, ch in enumerate(s):
        if ch in bad:
            continue
        if ch in good: # new repeat
            bad.add(ch)
            del good[ch]
        else:
            good[ch] = index

    if not good:
        return -1

    return min(good.values())

This is O(n) because the in lookups use hash tables, and the number of distinct characters should be much less than len(s).