I have a recursive function with a nested loop.I’m looking for what is the time complexity? Here is the function
def csFirstUniqueChar(input_str,letter = 0,num = 1):
if letter == len(input_str):
return -1
for x in range(len(input_str)):
if x == letter:
continue
if input_str[x] == input_str[letter]:
num += 1
if num == 1:
return letter
else:
return csFirstUniqueChar(input_str,letter + 1,1)
Advertisement
Answer
Suppose n is the length of input_str. The algorithm can iterate n times recursively in the worst case, i.e., in each recursive call letter will be increased by 1 and it can be continued up to n. In each iteration, the wors case is O(n) (running the loop completely). Hence, the time complexity is O(n^2).