Introduction to Algorithms
Introduction to Algorithms
3rd Edition
ISBN: 9780262033848
Author: Thomas H. Cormen, Ronald L. Rivest, Charles E. Leiserson, Clifford Stein
Publisher: MIT Press
Question
Book Icon
Chapter 2, Problem 1P

(a)

Program Plan Intro

To show that the insertion sort can sort the n/k sub lists, each of length k in Θ(nk) time.

(a)

Expert Solution
Check Mark

Explanation of Solution

The procedure of insertion sort in non-increasing order is as below:

INSERTION-SORT(A)

For j=2 to A .length

  key=A[j]

  i=j1

while i>0 and A[i]<key

  A[i+1]=A[i]

  i=i1

  A[i+1]=key

The j loop is running from 2 to the length of the array and then value in the index of array is stored in the key variable. After that the variable j is decreased by 1 and stored in the variable i.

Now, while loop is used in which two conditions are given: first condition is variable i is greater than 0 and the value of the array at index i must be less than key value.

The value at index i is swapped at the index i1 . The variable i is decreased by 1 and the key value is stored at the index i+1 . The only change in the insertion sort of non-decreasing order to non-increasing order is flip the condition.

Analysis:

The worst case running time of the insertion sort to sort a list of length n is Θ(n2) . Therefore, for sorting the n/k

sub lists of length k , the time taken by insertion sort is calculated as follows:

  Θ(k2nk)=Θ(nk)

Hence, the worst case running time of insertion sort to sort the n/k sub lists, each of length k is Θ(nk) .

(b)

Program Plan Intro

To show that the worst case running time to merge the sub lists is Θ(nlg(n/k)) .

(b)

Expert Solution
Check Mark

Explanation of Solution

There are n/k sub lists of length k and then merge the n/k sorted sub lists in a list of length n .

For this, take two sublists and merge them simultaneously. The time taken by this process is lg(n/k) steps. Now, compare n elements in each step.

Hence, the worst case running time to merge the sub listsis Θ(nlg(n/k)) .

(c)

Program Plan Intro

To find the largest value of k as a function of n so that the modified algorithm has same running time as standard merge sort.

(c)

Expert Solution
Check Mark

Explanation of Solution

Merge sort is a sorting algorithm that uses divide and conquer method. In merge sort, divide the input sequence in two halves and then sort them, Finally, merge the sorted halves.

The modified algorithm has same running time as standard merge sort if Θ(nlg(n/k))=Θ(nlgn) and consider that k=Θ(lgn) .

  Θ(nlg( n/k ))=Θ(nk+nlgnnlgk)=Θ(nlgn+nlgnnlg( lgn))=Θ(2nlgnnlg( lgn))=Θ(nlgn)

Hence, the running time of the modified algorithm has same as standard merge sort if Θ(nlg(n/k))=Θ(nlgn) and k=Θ(lgn) .

(d)

Program Plan Intro

To choose the value of k in practice.

(d)

Expert Solution
Check Mark

Explanation of Solution

Merge sort is a sorting algorithm that uses the divide and conquer method. In merge sort, divide the input sequence in two halves and then sort them. Finally, merge the sorted halves.

For considering the value of k, choose the largest length of sub list as kso that insertion sort becomes faster than merge sort.

Want to see more full solutions like this?

Subscribe now to access step-by-step solutions to millions of textbook problems written by subject matter experts!
Students have asked these similar questions
Q/ Fill in the table below with the correct answers for the network devices and components required, then draw the topology diagram for the network of this three-story building: I want a drawing Cisco Packet tracer Ground Floor: This floor will house the main server room, reception area, and a few conference rooms. The server room should contain the core network devices that will connect the entire building. The reception area and conference rooms need network access require access for mobile devices for visitors and guests with devices. First Floor: This floor is dedicated to offices with workstations, each needing reliable network connectivity for staff computers, IP phones, IP camera, and printers. Second Floor (Education Department): This floor consists of educational spaces requiring controlled internet access. Only the educational website (https://uokerbala.edu.iq) should be accessible, with all other sites restricted.. Device Media type Location floor Type of IP Static/dynamic…
Problem Statement You are working as a Devops Administrator. Y ou’ve been t asked to deploy a multi - tier application on Kubernetes Cluster. The application is a NodeJS application available on Docker Hub with the following name: d evopsedu/emp loyee This Node JS application works with a mongo database. MongoDB image is available on D ockerHub with the following name: m ongo You are required to deploy this application on Kubernetes: • NodeJS is available on port 8888 in the container and will be reaching out to por t 27017 for mongo database connection • MongoDB will be accepting connections on port 27017 You must deploy this application using the CL I . Once your application is up and running, ensure you can add an employee from the NodeJS application and verify by going to Get Employee page and retrieving your input. Hint: Name the Mongo DB Service and deployment, specifically as “mongo”.
I need help in server client project. It is around 1200 lines of code in both . I want to meet with the expert online because it is complicated. I want the server send a menu to the client and the client enters his choice and keep on this until the client chooses to exit . the problem is not in the connection itself as far as I know.I tried while loops but did not work. please help its emergent
Knowledge Booster
Background pattern image
Similar questions
SEE MORE QUESTIONS
Recommended textbooks for you
Text book image
Database System Concepts
Computer Science
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:McGraw-Hill Education
Text book image
Starting Out with Python (4th Edition)
Computer Science
ISBN:9780134444321
Author:Tony Gaddis
Publisher:PEARSON
Text book image
Digital Fundamentals (11th Edition)
Computer Science
ISBN:9780132737968
Author:Thomas L. Floyd
Publisher:PEARSON
Text book image
C How to Program (8th Edition)
Computer Science
ISBN:9780133976892
Author:Paul J. Deitel, Harvey Deitel
Publisher:PEARSON
Text book image
Database Systems: Design, Implementation, & Manag...
Computer Science
ISBN:9781337627900
Author:Carlos Coronel, Steven Morris
Publisher:Cengage Learning
Text book image
Programmable Logic Controllers
Computer Science
ISBN:9780073373843
Author:Frank D. Petruzella
Publisher:McGraw-Hill Education