1
$\begingroup$

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)?

$\endgroup$
  • 1
    $\begingroup$ We normally ask for code to be replaced by pseudocode, to make questions accessible to people who don't know the language that's being used. In this case, I suppose the Python is OK, since you've stated enough assumptions to answer the question without needing to understand the details of the code. $\endgroup$ – David Richerby Nov 30 '18 at 0:03
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.