Is this algorithm of constant time?

Question

I have the following code in Python:

def is_unique(string):
    if len(string) <= 1:
        return True

    if len(string) > 128:
        return False

    char_set = defaultdict(lambda: False)

    for char in string:
        if not char_set[char]:
            char_set[char] = True
        else:
            return False

    return True

It's basically checking if a string is unique or not. I think that my algorithm is O(1):

No matter what it's the length of the string, I will only iterate over at most 128 times in the worst case. All the operations (len, dict lookup etc) are of constant time as well.

I guess my generic question here is if you can proof that your algorithm will always iterate for a constant number of times, can you claim that this is O(1)?

Answer 1

Under the assumptions you've stated, yes, the code runs in constant time. The running time for any string can't be longer than the running time for a 128-character string, which is some constant number of steps.

Answer 2

You have to be careful with your assumptions, particularly the one on constant time dictionary lookup in the worst case. In general, this does not hold (see e.g., Wikipedia on hash tables). It depends precisely on the implementation details of the dictionary, but I would assume the general purpose dictionary implementation does not guarantee this.

With that being said, it seems that your setting is static so you can guarantee constant time lookups in the worst case by at least FKS hashing. In fact, you can more simply just use a direct access table instead of the dictionary.

Answer 3

Generally yes. I mean if an algorithm can run in $O(f(n)) = c$ time, where $c$ is a $constant$, then it is in $O(1)$ time.