Bitonic Sort (Calculating complexity)

Question

so basically I'm trying to understand how a time complexity of Bitonic Sort should be calculated and best and worse case scenarios decided using Cost and Time and then adding and multiplying values.

As an example: I tried first calculating complexity of Insertion sort.

        void sort(int A[]){                             Cost        Time

        for (int i = 1; i < A.length; i++)              c1          n
        {
            int key = A[i];                             c2          n-1
            int j = i-1;                                c3          n-1
            while (j >= 0 && A[j] > key){               c4          Σ (j=2 to n) of t_j
                A[j+1] = A[j];                          c5          Σ (j=2 to n) of (t_j-1)
                j = j-1;                                c6          Σ (j=2 to n) of (t_j-1)
            }
            A[j+1] = key;                               c7          n-1
        }
    }

t_j - is the amount of times "while" cycle is executed.

T(n) = c1*n + c2(n-1) + c3(n-1) + c4(Σ (j=2 to n) of t_j) +

+c5(Σ (j=2 to n) of (t_j-1)) + c6(Σ (j=2 to n) of (t_j-1)) + c7(n-1)

So in best case scenario t_j = 1, then: T(n) = an + b; (a, b - constants)

In worst case scenario t_j = j, then: T(n) = an^2 + bn + c;

So - O(n) - best case? O(n^2) - worse case ?

However I do not really understand what should be the cost and time of operations of bitonic sort methods and such, for example of the code like this:

   public class BitonicSorter implements Sorter
{
    private int[] a;
    private final static boolean ASCENDING=true, DESCENDING=false;

    public void sort(int[] a)
    {
        this.a=a;
        bitonicSort(0, a.length, ASCENDING);
    }

    private void bitonicSort(int lo, int n, boolean dir)
    {
        if (n>1)
        {
            int m=n/2;
            bitonicSort(lo, m, ASCENDING);
            bitonicSort(lo+m, m, DESCENDING);
            bitonicMerge(lo, n, dir);
        }
    }

    private void bitonicMerge(int lo, int n, boolean dir)
    {
        if (n>1)
        {
            int m=n/2;
            for (int i=lo; i<lo+m; i++)
                compare(i, i+m, dir);
            bitonicMerge(lo, m, dir);
            bitonicMerge(lo+m, m, dir);
        }
    }

    private void compare(int i, int j, boolean dir)
    {
        if (dir==(a[i]>a[j]))
            exchange(i, j);
    }

    private void exchange(int i, int j)
    {
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }

}

Maybe anyone has ever tried calculating complexity of this Sort algorithm and could either give an example of Costs and Time? or reference to understanding what costs and times should be attributed ?

P.S I'm new to this and do not properly understand how it should be "calculated", so feel free to give suggestions. Appreciate.

Answer 1

To analyze recursive procedures, you need to write and solve a recurrence. Here, let S(n) be the number of comparisons to sort n elements and M(n) be the number of comparisons to merge n elements.

           S(1) = 0
for n > 1, S(n) = 2 S(n/2) + M(n)
           M(1) = 0
for n > 1, M(n) = 2 M(n/2) + n/2

We can use the Case 2 of Master Theorem to solve these.

M(n) = Theta(n log n)
S(n) = 2 S(n/2) + Theta(n log n) = Theta(n (log n)^2)