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.