Answered: Which of these two algorithms has a…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

Which of these two algorithms has a better big-O run-time? For each, list the big-O run-time notation for each and how you determined it.

def gnomesort(seq):
i=0
while i<len(seq):
if i==0 or seq[i-1]<=seq[i]:
i+=1
else:
seq[i], seq[i-1] = seq[i-1], seq[i]
i-=1

and

def mergesort(seq):
mid=len(seq)//2
l,r=seq[:mid],seq[mid:]
if len(l)>1: l=mergesort(l)
if len(r)>1: r=mergesort(r)
res=[]
while l and r:
if l[-1] >= r[-1]:
res.append(l.pop())
else:
res.append(r.pop())
res.reverse()
return (l or r) + res

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 3 steps with 1 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions