Time complexity analysis

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 1

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.

Answer 2

Well searching an element in the array sequentially has a time complexity of O(n) in the worst case scenario because you imagine traversing through the whole list to get an element at the end or to find out the element you are searching for does not exist. O(n) is because the operation of searching grows linearly as the array size grow. In the worst case for 100 array elements you take 100 operations and for 1000000 array elements you take1000000 operations etc. There are several algorithms for searching and sorting and each has a different time complexity but the above example may enlighten you on how the concept is done. Visit the Web for more e.g. https://www.geeksforgeeks.org/time-complexities-of-all-sorting-algorithms/amp/