I have a recursive function with a nested loop.I’m looking for what is the time complexity? Here is the function
JavaScript
x
13
13
1
def csFirstUniqueChar(input_str,letter = 0,num = 1):
2
if letter == len(input_str):
3
return -1
4
for x in range(len(input_str)):
5
if x == letter:
6
continue
7
if input_str[x] == input_str[letter]:
8
num += 1
9
if num == 1:
10
return letter
11
else:
12
return csFirstUniqueChar(input_str,letter + 1,1)
13
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)
.