Analysis of sort_bitonic, Computer Networking

The bitonic sorting network needed log n number of stages for performing the task of sorting the list. The first n-1 stages of the circuit are able to sort two n/2 numbers and the last stage uses a +BM (n) comparator having the depth of log n. As running time of the sorting is dependent upon the entire depth of the circuit, thus it can be depicted as:

D (n) = D (n/2) + log n

Answering the above mentioned recurrence relation

D (n)= (log2 n + log n)/2  = O(log2 n)

Thus, the complexity of solving a sorting algorithm using a combinational circuit is

O (log2 n).

 

Posted Date: 3/2/2013 6:43:28 AM | Location : United States







Related Discussions:- Analysis of sort_bitonic, Assignment Help, Ask Question on Analysis of sort_bitonic, Get Answer, Expert's Help, Analysis of sort_bitonic Discussions

Write discussion on Analysis of sort_bitonic
Your posts are moderated
Related Questions
A mobile host (MH) is connected to a WLAN access network that uses MIP for mobility support. Consider that the RTTs between MH and HA are 0.3s while RTTs within a L2 subnet are 80

Q. Illustrate Data-Link Layer in osi layers model? Data-Link Layer: This layer takes the data messages or frames from the Network Layer and gives for their actual transmissio

Quetion: A 22 nF capacitor is initially charged to 10V. It is then discharged by connecting a 100kW resistor across it. Approximately how long does it take for the voltage on t

Q. Explain Session Layer in osi model? - The session layer defines how to control, start and end conversations (called sessions) between applications. - This includes the c

Benefits of Building up a well-designed Intranet Building up a well-designed Intranet can help the companies in the following activities that would improve their overall perfor

The major problems with multiple networks are as given: A computer attached to a given server can only interact with other computers attached to the similar network.


Simple Mail Transfer Protocoland Secure Sockets Layer SMTP: Simple Mail Transfer Protocol is a server-to-server protocol for delivering electronic mail. SSL: Secure Sockets

Explain the meaning of Disassociation A notification from either a station or an AP that an existing association is terminated. A station should provide this notification befor

Parallel Programming Environment Characteristics  The parallel programming environment consists of an debugger, a editor,  performance evaluator and programme visualizer for i