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
Transport Layer In computer networking it the transport  layer is where  sessions are  exchanged between  hosts. This layer resides  between  the application layer and  networ

Protocol Layering To design  structural  network protocols the designers organize protocol and use the network  hard ware and software to implement  the protocol  in layers. E

The Physical layer deals with the definite physical medium and the method of transporting 1s and 0s.

Residential Access Residential  access is connecting home  end  systems ( typically a PC but increasingly a home network) into the network. One form  of residential  access  i

Q. Show the Traffic profiles? Constant-bit-rate traffic - ADR=PDR No MBS Variable-bit-rate traffic ADR != PDR Small MBS Bursty traffic

Communication is the process of sending and receiving data by means of a data cable that is associated externally. Transmission means the transmitting of data from the source to

Why do we require to subtract two from number of hosts?

What is basic purpose of Routers

Consider the similar conditions as the last problem, except for the following: what's the minimum possible response time for the 1 Gbps and a 1 Mbps line?  What does the diffrentia

Advantages of LS over DV algorithm There  are a number of advantages to link  state  protocols  especially when  compared to  the distance vector based  routing  protocols. The