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
Explanation:- In functional testing, you require to confirm that the objects in the application-under-test look and work as designed from build to build. To accomplish this, yo

what is the work of pin daigram in 8086 microprocessor in assembly

Paged virtual memory: Mostly all implementations of virtual memory divide the virtual address space of an application program into pages; a page is a block that contains conti

Evidence of intelligent behavior - Artificial Intelligence: Machines mean they could simply be personal computers, or they could be robots with embedded automative systems, or

Assume that a graph has a minimum spanning tree already computed.  How fastly can the minimum spanning tree be updated if a new vertex and incident edges are added to G? If the

Subscript refers to the array of occurrence, whereas Index shown an occurrence of a table element. An index can only modified using perform, search & set. Require to have an index

Objectives After going through this unit, you will be able to : Tell historical facts of parallel computing; Can explain the essential concepts of the discipline, e.g.

A piece of art can be looked at as having 3 main components, the subject, the composition and the content. Subject The subject of an artwork is, in simple terms, the object

Q. Show Programming Based on Data Parallelism? In data parallel programming model the focal point is on data distribution. Every processor works with a part of data. We will co

Define the concept of Typing of object oriented analysis Typing enforces object class such that objects of different classes cannot be interchanged.  Or we can say that, class