is the code's complexity supposed to be O(log n) even if the entire list is in "steady state", or does it refer only to the non- steady part of the list?
The thing is- if I know that list[i]==i and that list[i+2]==2 I have to check list[i+1]. It's a linear checking process, and all the lions and the deserts won't help it become O(log n) as far as I know.
You may use recursion if you like.
BUT - if you do use recursion please make sure your code runs in O(logn) time (beware of slicing)
you said to be ware of slicing - why? if I use slicing (not in a recursive function) will it be considered O(n)?
Is the code suppose to handle negative numbers as well? for example
steady_state([-9, -8, -1])
should return -1?
I can't edit the last question , so I'm just writing it here…
Is there a difference whether I recall the function from (a) to be used in (b) or just edit the function from (a) so it'll suit my needs in (b)? especially in terms of grading my code…
Your function in (a) should do what we ask, regardless of whether you want to use it in section (b).
But you may plan your solution to (a) with respect to what you'll need in (b).
in (b): if in the worst case all of the elements of L are such that L[i]==i, how can i have a program more efficient than O(n)? i mean that in the worst case we have to go over the whole list.
can we assume that the input is valid : integers in a growing order?
what should the function in (a) return if L=?