CODEWITHSUNDEEP
pythonalgorithm
Ritika Manwani
Ritika Manwani

Reputation: 13

Complexity of the python code

I am trying to find the runtime complexity of this Python program. Will the complexity be still n or will it be more than n as I am creating a new list for each recursive call

def RecLinearSearch(lyst,number):
    found = False
    index = len(lyst)-1
    if lyst[index] == number:
        found = True
        return found
    elif index<len(lyst)-1:
        index +=1
        return RecLinearSearch(lyst[index:],number)
    return found
print(RecLinearSearch([1,4,5,65,44],55))

Upvotes: 1

Views: 89

Answers (2)

Eric Duminil
Eric Duminil

Reputation: 54223

Your original code was broken. It only required 1 step and checked if the last element is the desired number. It was O(1) but didn't do what the function name implies it should do. The recursive call never happened, and the lyst was never sliced.

Your updated code runs in O(n**2) : the worst case would be n slices at the n/2th index on average. It's slower than necessary, and due to the recursive calls, it's not possible to say at which index the number has been found.

If you passed the last index as argument and would leave the lyst untouched, it could run in O(n). But then, you also wouldn't need recursive call, just a simple loop.

With a sorted lyst, it could run in O(log n) with a binary search.

Upvotes: 2

Stefan Pochmann
Stefan Pochmann

Reputation: 28606

Time and space complexity of your function are both O(1), since index<len(lyst)-1 is always false.

Upvotes: 5

Related Questions