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
Explain the working of Transceivers Transceivers are used to connect nodes to the several Ethernet media. Most computers and network interface cards having a built-in 10BaseT o

Q. Show the Parity Check - Performance? Parity Check - Performance Is able to detect all single-bit errors Can as well detect burst errors if the total number of

SQL is a powerful set-oriented language which was developed by IBM research for the databases that adhere to the relational model. It having of a short list of powerful, yet highly

What is a computer network? Computer Network is a collection of distributed intelligent devices that are connected with each other with transmission media for the purpose of da

Q. Host System in TCP-IP model? - Standards adopted because of widespread use like (Internet) - The protocols came first plus the model was really just a description of the

Types of VTs There are  several  option for  payload are actually mapped into the VT.  Locked mode VTs  bypass the pointers with a fixed  byte oriented mapping of limited flexi

State the Software requirement for an intranet To develop an Intranet the first we should design a Client /Server model for our network. As you know clients are the computers

ENCODING THE DATA TYPE: The figure explain a frame in which the data kind is specified by using the data area. To ensure interoperability format of encoding location m

FDDI -(Fiber Distributed Data Interface) FDDI Basics: FDDI (Fiber Distributed Data Interface) came about because system managers became concerned with network reliability i

The Five steps to data encapsulation (IN ORDER): 1) User information is changed into data. 2) Data is changed into segments. 3) Segments are changed into datagram and pack