HW3 Q5
Main Thread
HW3 Q5
Forum
» Discussions. / Q&A, Fall 2014
» HW3 Q5
What do you mean by writing O(logn)?
Is it log2(n)?
As we discuss in the recitations, the log base doesn't matter in this case.
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.
It should be O(logn) in the worst case.
Try to figure out how…
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)?
Remember what we saw about slicing - it creates a copy of the slice. Look again at the slides on iterative binary search from the lectures.
can I assume that the list is already sorted?
Is the code suppose to handle negative numbers as well? for example
steady_state([-9, -8, -1])
should return -1?
steady_state([-9, -8, -1]) should return something else - read the question carefully again please.
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.
I may seem impossible, but it isn't.
(Think how not to go over all the elements.)
can we assume that the input is valid : integers in a growing order?
Yes. Whenever we do not say otherwise, you may assume the input is valid.
what should the function in (a) return if L=[]?
it should return None (but we will not include this case in our tests).
/forum/t-723964/hw3-q5#post-