0
$\begingroup$

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;
  }
}    
}
$\endgroup$
  • $\begingroup$ where is the sortUsingDLL method ? I think you meant sortUsingDLLWODup $\endgroup$ – Ahmad Bazzi Sep 12 '18 at 1:19
  • 1
    $\begingroup$ We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered. $\endgroup$ – Raphael Sep 12 '18 at 5:45
  • 1
    $\begingroup$ Please get rid of the source code and replace it with ideas, pseudo code and arguments of correctness. See here and here for related meta discussions. $\endgroup$ – Raphael Sep 12 '18 at 5:46
  • $\begingroup$ Also, not that the phrase "Big O notation for Sorting Algorithm" contains a layered type error. There is no such thing. $\endgroup$ – Raphael Sep 12 '18 at 5:46
  • $\begingroup$ Your code may lead to null reference exceptions $\endgroup$ – Navjot Singh Sep 12 '18 at 11:35
2
$\begingroup$

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)$$

$\endgroup$
  • 1
    $\begingroup$ Why? Can you give a sketch of the analysis? $\endgroup$ – Raphael Sep 12 '18 at 5:47
  • $\begingroup$ I know this is out of scope for the question but can you tell me also the best and average case. With the analysis if possible. Thanks Ahmad! $\endgroup$ – nader Sep 12 '18 at 16:08
1
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ Why? Can you give a sketch of the analysis that goes beyond looking at an example of size 10? $\endgroup$ – Raphael Sep 12 '18 at 5:47
  • $\begingroup$ @Raphael Well for any array of size $n$, where the array is ordered such that it is increasing, each element $n$ will have to perform $n+1$ comparisons. The number of comparisons will follow the previously stated sum in my answer. $\endgroup$ – Chuck Sep 12 '18 at 12:42
  • $\begingroup$ And why is that the worst case? $\endgroup$ – Raphael Sep 13 '18 at 5:45
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.