Time complexity for recursive functions

Question

How to count the time complexity for this? Should I count it for to functions separately?

def recursive_function2(mystring,a, b):
    if(a >= b ):
        return True
    else:
        if(mystring[a] != mystring[b]):
            return False
        else:
            return recursive_function2(mystring,a+1,b-1)

def function2(mystring):
    return recursive_function2(mystring, 0,len(mystring)-1)

Ryan · Accepted Answer · 2022-10-05 01:12:47Z

1

Big O is the worst case time complexity of how many times your loop (a recursive function in this case) will iterate based on input parameter of size N. In your recursive function, the worst case is that it iterates until a >= b. For an input string of size N, that means your recursive function in the worst case runs N/2 times, for arbitrarily large N we drop coefficients so your function is O(N)

answered Oct 5, 2022 at 1:12

Ryan

1846 bronze badges

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

Collectives™ on Stack Overflow

Time complexity for recursive functions

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