Analysis of sort bitonic, Computer Engineering

Analysis of Sort_Bitonic(X)

The bitonic sorting network needs log n number of phases for performing task of sorting the numbers. The first n-1 phases of circuit can sort two n/2 numbers and the last phase uses a +BM (n) comparator having the depth of log n. As running time of sorting relies upon the total depth of the circuit so it can be stated as: 

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

  Solving above written recurrence relation

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

  So the complexity of solving a sorting algorithm employing a combinational circuit is O (log2n).

 One more famous sorting algorithm called merge sort based algorithm can also be solved with help of combinational circuit.

Posted Date: 7/10/2013 7:47:24 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
What is the functionality of Remote Login? Remote Login gives similar functionality of telnet, along with the added functionality of not involving a password from trusted cli

(a) What is Grid computing? (b) What are the key distinctions between conventional distributed computing and Grid computing? (b) Describe how five features of Grid Computi

The general method for constructing the parameters of the RSA cryptosystem can be described as follows: Select two primes p and q Let N = pq and determine ∅ (N) = (p - 1

Write a GUI/MP3 program called MP3Random that reads all MP3 les in a directory and plays them in random order. The GUI should have a little window with: 1. A button Next that s

First Generation Electronic Computers (1937-1953) Three machines have been promoted at different times as first electronic computers. These machines used electronic switches

What is a transaction? A transaction is dialog program that alter data objects in a consistent way.

What is refactoring? Refactoring is explained as the changes to the internal structure of software to improve its design without changing its external functionality. It is an e

Postpurchase Interaction Customer service and support: The considerations at this stage can be explained by the following example: Consider a bundle having of a portfolio

A source is an object that produces an event. This happens when the internal state of that object changes in some way. A listener is an object that is notified when an event happen

What is Anonymous File Transfer Protocol? Anonymous FTP: While a FTP client contacts a server, in that case, the daemon will ask for an account number or username and it