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
Chandella07
  • 2,089
  • 14
  • 22
A.Lee
  • 265
  • 2
  • 9

1 Answers1

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

Victor Cui
  • 1,393
  • 2
  • 15
  • 35