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
Can you delete a domain, which is being used by data elements? No.

Explain the term- Looking at existing paperwork This allows analyst to see how paper files are kept and look at operating instructions and check accounts, training manuals etc

Interfacing Subroutines with Parameter Passing Let's now write a C program which calls the assembly program for parameter passing. Let's extend the previous two programs such t

The number and nature of registers is a major factor which distinguishes among computers. For illustration, Intel Pentium has about 32 registers. A number of these registers are sp

There is a built-in function function known as cellfun that evaluates a function for each element of a cell array.  Make a cell array, then call the cellfun function, passing the h

a. Define the meaning of "Document & Finger print" and "Message & Message Digest". What's the difference among the 2 pairs? b. Describe Davies Meyer scheme with diagram. c. W

Computer Architecture Basics: Some of computer architecture at companies such like AMD and Intel uses more fine distinctions: Macro architecture- this is an architectura

Obstacles to IS implementation While information systems are now becoming the norm in most organisations the journey to this point has been a difficult one. Even in the 21st c

Q. Editor - Tools necessary for assembly language programming? The editor is a program which allows the user to enter and modify as well as store a group of instructions or tex

Before 1994 there were dissimilar methodologies like Rumbaugh, Booch, Jacobson, and Meyer etc who followed their own notations to mould the systems. The developers were in a di