Big O notation for Sorting Algorithm

Question

I am interested to know whether the time complexity of following algorithm is $O(n^2)$ or $O(n\log n)$.

Here is the implementation:

public class HelloWorld
{

 public static void main(String[] args)
 {

    Hello hw = new Hello();
    int[] n = {2,3,4,52,5,63,0,664,2,2,56,68,8};
    hw.sortUsingDLLWODup(n);
 }
}

public class Node
{
   public int value;
public Node next;
public Node prev;
public Node(int v) {
    value = v;
}
}

public class Hello
{

public void sortUsingDLLWODup(int[] n) {

int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int i = 0;i<n.length;i++) {
if(max<n[i])max = n[i];
if(min>n[i])min = n[i];
}

Node root = new Node(min);
Node end = new Node(max);
root.next = end;
end.prev = root;

for(int i = 0;i<n.length;i++)
{
    Node current = root;
    while(n[i]>current.value && current!=null) {
        current = current.next;
    }
    if(current!=null&&current.value>n[i]) {
        Node temp = current.prev;
        Node newNode = new Node(n[i]);
        temp.next = newNode;
        newNode.prev = temp;
        newNode.next = current;
        current.prev = newNode;
    }
}
Node test = root;
while(test!=null){

System.out.println(test.value);
test = test.next;
  }
}    
}

Answer 1

You will have $O(n^2)$ in worst case. Actually what you do is really close to insertion sort. Worst case is attained when you got the array in decreasing order.

\begin{align} T(n) &= T(n-1) + n\\ &=T(n-2) + n-1 + n \\ &= \vdots \\ &=T(n-k) + \sum_{i=0}^k (n - i) \end{align} Algorithm terminates at $k = n$, i.e. we shall get $$T(n) = T(0) + \sum_{i=0}^n (n - i)$$ where $T(0) = O(1)$. So, upon a change of variable, we get $$T(n) = \sum_{i=0}^n i = \frac{n(n+1)}{2} = O(n^2)$$

Answer 2

The worst case will be $O(n^2)$ for the situation where each inserted number is greater than the previous number. This situation can be seen with an input array of ${1,2,3,4,5...10}$. You insert $1$, which must be compared with the min node and max node you set. Therefore, this is $2$ comparisons. The next number, $2$, must be compared with every number in the array since it will be the second largest number (next to the MAX_VALUE node). This comparisons increase for the next number $3$ for the same reason.

Thus, the number of comparisons you have is effectively $2+3+4..+n+n+1 = n(n-1)/2 = O(n^2)$.

Answer 3

The worst case will occur when the elements of your array are already sorted i.e. already in ascending order.

Let the sequence be {1,2,3,4,5,6}. So initially the list will be like 1 -> 6 , since we are fixing the min and max elements. Now first taking in account the comparisons for non min and non max elements i.e. 2,3,4,5.

1. For 2, we will have two comparisons (one with 1 and one with 6). Now with insertion of 2, the list becomes 1 -> 2 -> 6.

2. For 3, we will have three comparisons (with 1, 2 and 6). Now the list is 1 -> 2 -> 3 -> 6.

3. Similarly for 4, we will have four comparisons and for 5 we will have five comparisons.

Now let us take in account the comparisons for min and max element. Since your algorithm makes comparison for them as well (which can certainly be optimized as you need not check for min and max elements).

The comparison count for min element is one, when we compare 1 with 1 itself. The comparison count for max element is n.length (length of the array) because we will need to compare it with each element in the list and with itself.

So, generalizing the number of comparisons and taking len = n.length, we have:

$$\sum_{i=1}^{len} i = len^2$$

So worst case complexity will be $O(len^2)$ where len is the length of the array to sort.