CODEWITHSUNDEEP
python-3.xperformancetime-complexity
Despasita
Despasita

Reputation: 13

efficiency of algorithm - are all string elements unique

The task: Implement an algorithm to determine if a string has all unique characters.

I wrote two functions that dose that. How do I start to asses which one is better/more efficient? what are the things to look for?

this is the first one:

def is_unique(word):
    start = 0
    len_word = len(word)

    while start < len_word:
        for i in range(start + 1, len_word):
            if word[start] == word[i]:
                return False
        start += 1
    return True

second one:

def unique_list(word):
    unique = []

    for i in word:
        if i in unique:
            return False
        else:
            unique += i
     return True

Upvotes: 1

Views: 27

Answers (1)

J&#233;r&#244;me Richard
J&#233;r&#244;me Richard

Reputation: 50488

Both algorithms are inefficient: their complexity is O(n^2) with n the number of character in word. The second algorithm will be a bit faster in practice because it uses the build-in Python operation i in unique (rather than slow CPython loops).

The test can be done in a much faster way: len(set(s)) == len(s). This line tests if the string contains unique characters in O(n) (since the string characters can be converted to a set in linear time).

Upvotes: 2

Related Questions