precondition list exam Dec 2011 Question 5
Author Message
c3shahie Offline
Student


Reputation: 0
Post: #1
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?
2014-04-25 00:21
Find all posts by this user Quote this message in a reply
tff Offline
Instructor


Reputation: 1
Post: #2
RE: precondition list exam Dec 2011 Question 5
(2014-04-25 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.
2014-04-25 06:43
Find all posts by this user Quote this message in a reply
Post Reply 
 
Thread Rating:
  • 0 Votes - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5


Forum Jump:


User(s) browsing this thread: 1 Guest(s)