Complexity of the python code

Question

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

@EricDuminil whoops. Wasn't reading carefully. Was assuming the function worked as intended... — juanpa.arrivillaga, Apr 01 '17 at 11:13
Lesson learned from this question: make sure the code does what it is supposed to do before posting. Now *O(1)* is the only correct answer. — trincot, Apr 01 '17 at 11:15
@juanpa.arrivillaga What you just said makes no sense, as linear implies O(n^2). — Stefan Pochmann, Apr 01 '17 at 11:15
@juanpa.arrivillaga: It would be `O(n**2)`, I don't see how `lyst[index:]` could be `O(1)` — Eric Duminil, Apr 01 '17 at 11:16
@StefanPochmann ... I am [pretty sure linear](https://en.wikipedia.org/wiki/Time_complexity#Linear_time) implies O(n) ... ? — juanpa.arrivillaga, Apr 01 '17 at 11:17
@juanpa.arrivillaga It *also* implies O(n), yes. But *every linear function is also O(n^2)*. — Stefan Pochmann, Apr 01 '17 at 11:19
That is the exact same question I am trying to ask. Will it be O(n^2) as I am using lyst[index:] — Ritika Manwani, Apr 01 '17 at 11:20
@StefanPochmann: Okay. Technically, linear is also O(n!) and O(n**n**n**n). It's not very helpful, though. — Eric Duminil, Apr 01 '17 at 11:21
Yes, actually I think it's quadratic now. Sorry, it's late where I am. But I'm still not following @StefanPochmann — juanpa.arrivillaga, Apr 01 '17 at 11:21
@RitikaManwani: You'll have to fix your code first. Right now, it's broken and returns too soon. — Eric Duminil, Apr 01 '17 at 11:21
@juanpa.arrivillaga Big-O is about upper bounds. If something costs less than $10, it also costs less than $100. What you said is like saying it doesn't cost less than $100 but it does cost less than $10. That's wrong. — Stefan Pochmann, Apr 01 '17 at 11:22
@juanpa.arrivillaga: `O()` only gives an information about a maximum boundary, not about a range. If you say you can do the laundry in 2h, it's also technically correct to say you can do it in 6 months. — Eric Duminil, Apr 01 '17 at 11:23
@juanpa.arrivillaga: See this [thread](http://stackoverflow.com/questions/471199/what-is-the-difference-between-%CE%98n-and-on) — Eric Duminil, Apr 01 '17 at 11:24
@RitikaManwani yeah, use `.pop()` instead so you can scale linearly. — juanpa.arrivillaga, Apr 01 '17 at 11:36

score 5 · Answer 1 · answered Apr 01 '17 at 11:12

5

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

answered Apr 01 '17 at 11:12

Stefan Pochmann

27,593
8
44
107

Eric Duminil · Accepted Answer · 2017-04-01T11:31:35.920

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.

Complexity of the python code

2 Answers2