What\'s the right answers? Includes all the steps Problem 1) Suppose we are comp

Question

What's the right answers? Includes all the steps Problem 1) Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in 8n 2 steps, while merge sort runs in 64n lg n (i.e, log in base 2) steps. For which values of n does insertion sort beat merge sort? Problem 2) Comparison of running times For each function f(n) and time t in the following table, determine the largest size n of a problem that can be solved in time t, assuming that the algorithm to solve the problem takes f(n) microseconds (lg indicates log in base 2): second minute hour day month yearcentury lg n 7l /n nlg n 2 2"

Explanation / Answer

def insertionSort(alist):
for index in range(1,len(alist)):

currentvalue = alist[index]
position = index

while position>0 and alist[position-1]>currentvalue:
alist[position]=alist[position-1]
position = position-1

alist[position]=currentvalue

alist = [54,26,93,17,77,31,44,55,20]
insertionSort(alist)
print(alist)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.