precondition list exam Dec 2011 Question 5

Author 
Message 
c3shahie
Student
Reputation: 0

precondition list exam Dec 2011 Question 5
Give a bound on the worst case running time of each algorithm below....
# precondition: L is a list and n = len(L)
while i < n:
print L[i]
i > i*2
Should we assume that the list is not empty?


20140425 00:21 

tff
Instructor
Reputation: 1

RE: precondition list exam Dec 2011 Question 5
(20140425 00:21)c3shahie Wrote: Give a bound on the worst case running time of each algorithm below....
# precondition: L is a list and n = len(L)
while i < n:
print L[i]
i > i*2
Should we assume that the list is not empty?
Well, I don't think that you need that condition. If n = 0, the loop won't be entered, so there won't be an array index out of bounds issue. If your concern is evaluating log(n) for n = 0, don't worry about that  you can just set your breakpoint B to be larger than 0.
My memory is that there is a typo in that question  you need to initialize i to 1 not 0.


20140425 06:43 

Thread Rating:
 0 Votes  0 Average
 1
 2
 3
 4
 5
User(s) browsing this thread: 1 Guest(s)