An answer to this question on the Scientific Computing Stack Exchange.

Question

I want to know the time complexity of following code

Say I have a list unique_element[]

There is an array which contain elements {4,5,2,4,7,8,1,5,9,8,1}

Now as per my code I want to find out the unique element from this array and store this element into the unique_element[] list

for(int i=0;i<arr.length.i++){
     loop body //[This code block to find the unique element]
}

Now after finding the unique element from the array and store those element into the unique_element[]list my next task is to sort the unique_element[] list.

For that, again, I create a for loop

for(int j=0;j<unique_element[].length;j++){
 loop body to sort unique_element[]
}

Now I want to calculate the time complexity of this program. I am confuse between O(n^2) and O(n). Because there is two loop so it may be O(n^2) but as per my knowledge if there is nested for loop then time complexity will be O(n^2). Here in my program there are two for loops however they are independent for loops. So there is a fair chance that time complexity will be O(n).

Which one is correct O(n^2) or O(n)?

Thank you in advance.

Answer

It's O(n), but it depends on the sorting algorithm you use. Finding unique elements is O(n) with a hash table. You use one for loop to count incidents and a subsequent loop to extract uniques.

Sorting should be offloaded to a library algorithm, so a for loop isn't necessary. Using insertion sort or its ilk would require two loops for O(n^2) time, though you'll get good performance for small datasets. Most sorting algorithms run in O(n log n) time, but can't be easily expressed using simple loops. But, since you've got integer data, you can use social purpose sorting algorithms like radix, which give O(n) time.