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) = (log² n + log n)/2 = O (log² n)

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

 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

Ask an Expert

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

Write your message here..

Related Questions

What is the functionality of remote login, What is the functionality of Rem... 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

What is grid computing, (a) What is Grid computing? (b) What are the k... (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

Rsa encryption function- cryptography, The general method for constructing ... 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

Create a complete mp3 player, Write a GUI/MP3 program called MP3Random that... 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

Explain in detail about first generation electronic computer, First Generat... 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, What is a transaction? A transaction is dialog ... What is a transaction? A transaction is dialog program that alter data objects in a consistent way.

What is refactoring, What is refactoring? Refactoring is explained as t... 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, Postpurchase Interaction Customer service an... 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

What is source and listener, A source is an object that produces an event. ... 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, What is Anonymous File Transfer P... 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