Analysis of merge sort, Computer Engineering

Assignment Help:

i) The width of the sorting + merging circuit is equivalent to maximum number of devices needed in a phase is O(n/2). As in the above diagram maximum number of devices for a given phase is 4 that is 8/2 or n/2. 

ii) The circuit comprises two sorting circuits for sorting sequences of length n/2 and afterwards one merging circuit for merging of two sorted sub sequences (see phase 4th  in above figure). Let functions Tm and Ts signify the time complexity of merging and sorting in terms of its depth.

The Ts can be calculated as follows:  

               Ts (n) =Ts (n/2) + Tm (n/2) 

               Ts (n) =Ts (n/2) + log (n/2), 

 Therefore, Ts (n) is equal to O (log2 n).

2264_Analysis of Merge Sort.png

Figure: Sorting + Merging Circuit


Related Discussions:- Analysis of merge sort

gui component handle its own events, A component can handle its own events...

A component can handle its own events by executing the needed event-listener interface and adding itself as its own event listener.

Multiple bus architecture - computer architecture, Multiple bus architectur...

Multiple bus architecture: One solution to the bandwidth restriction of a single bus is to simply add extra buses. Consider the architecture indicated in given figure that con

Branch (control) hazards in computer architecture, Branch (control) hazards...

Branch (control) hazards in computer architecture : Branching hazards (also called control hazards) take place when the processor is told to branch -for example, if a defin

Usability test of website, For this part of your assessment you are require...

For this part of your assessment you are required to prepare and conduct a usability test of the website that you have chosen to review from Part A . You must design the script,c

What are the facilities of a debug monitor, What are the facilities of a de...

What are the facilities of a debug monitor? The facilities of a debug monitor are given below: a. Setting breakpoints into the program b. Initiating a debug conversation

Reflexes - artificial intelligence, Reflexes - artificial intelligence: ...

Reflexes - artificial intelligence: If an agent decides upon and executes an action in response to a sensor input without consultation of its world, then this can be considere

Which technique allows executing a program not in memory, A set of techniqu...

A set of techniques that allow executing a program which is not entirely in memory is called ? Ans. virtual memory which allows executing a program that is not entirely in me

What is master slave kernel, Q. What is Master slave kernel? Master sl...

Q. What is Master slave kernel? Master slave kernel: In this model just one of processors is assigned as Master.  The master is in charge for subsequent activities:  i)

How to add a wait state when creating a verification point, 1. Start to mak...

1. Start to make the verification point. 2. In the confirmation Point Name dialog box, select Apply wait state to confirmation point. 3. Type values for the following option

Can we run matlab without graphics, Sometimes you may need to run scripts w...

Sometimes you may need to run scripts which have plotting commands without displaying the plots and without going into the script to comment out the commands. An example: if you're

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd