0

i am trying practice some coding question and wondering how I can calculate big O for following code string[i] in string[i+1:] and string[i] not in seens

def findNoCurring(string):
    seens = set()
    for i in range(len(string)):
        if not string[i] in string[i+1:] and string[i] not in seens:
            return string[i]
        else:
            seens.add(string[i])
    return None
1
  • 1
    It's O(n) for strings. You have to look at every character of the string. Oct 29, 2018 at 3:21

1 Answer 1

1

The line string[i] in string[i+1:] will make your algorithm O(N^2). With this line, you're checking every character in the string with every other character. If string = "abcd", you're checking a against b, c, d, then b against c, d, and so on. the line string[i] not in seens will be O(1) on average since Python sets are implemented something like dictionaries (see the answer here).

Note that the in operation for Python lists, is, on average, O(N). See this

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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