what is the Time Complexity of a nested loop in a recursive function?

Question

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)

OmG · Accepted Answer · 2020-10-28 20:35:02Z

2

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

answered Oct 28, 2020 at 20:35

OmG

19k13 gold badges69 silver badges96 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

what is the Time Complexity of a nested loop in a recursive function?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related