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