CODEWITHSUNDEEP
pythonfor-loopbig-olist-comprehension
sgeza
sgeza

Reputation: 361

Python - Big(O) Runtime: List Comprehension & For Loop

In CTCI(Python version), the runtime of the code below is described to be O(N)

# O(N)

def unique(string):
    # Assuming character set is ASCII (128 characters)
    if len(string) > 128:
        return False

    char_set = [False for _ in range(128)]
    for char in string:
        val = ord(char)
        if char_set[val]:
            # Char already found in string
            return False
        char_set[val] = True

    return True

This really confuses me as I see a list comprehension in the formation of char_set and another for loop right after... shouldn't the run-time be O(N ^ 2)?

Edit: I'm also confused as to why Laakman uses len(string) > 128 to check for ascii char. Wouldn't that just give the length of the string in question and not the character value which the ord method in Python gives?

Edit1: Can the same be achieved if she doesn't use val = ord(char) ? That would change the next line to if char_set[char]:

Upvotes: 0

Views: 685

Answers (2)

Daniel Roseman
Daniel Roseman

Reputation: 599796

For your second question, the point is that this code is intended to check that every character in the string is unique. Assuming that the string is ASCII, if it is longer than 128 characters it cannot possibly contain only unique characters since there are only 128 characters in the ASCII charset to begin with.

Upvotes: 1

blhsing
blhsing

Reputation: 106945

The amount of time [False for _ in range(128)] takes is fixed and therefore has a time complexity of O(1).

Upvotes: 1

Related Questions