Algorithm for better Big O complexity [duplicate]

Question

This question already has answers here:

Best case Big O complexity (2 answers)

Closed 9 years ago.

Could someone please help me with this question?:
how can you limit the input data to achieve a better Big O complexity? Describe an algorithm for handling this limited data to find if there are any duplicates. What is the Big O complexity?

By limit the input data, we mean the array size e.g. n=100 (array contains 100 integers) and also; the array is unsorted by default but could be implemented in the algorithm.

The worst case complexity which i got is O (N^2) = N * ((N + 1)/2) in the case of an unsorted array of size n.

I got that by using nested loops (outer loop used for n-1 iterations- used to iterate on each value in the array- and the inner loop used for comparison to check to see if duplicates exist) and repeated the process until the outer loop terminates.

Answer 1

You have the solution right in front of you. As you state, if the array is unsorted, finding duplicates is O(N^2). But if the array is sorted, you can do it in O(N). So sort the array first, which can be done in O(N.Log(N)).

An algorithm that first sorts and then find the duplicates can thus be done in O(N.Log(N) + N), which is O(N.Log(N)).

UPDATE:

As Amir points out: you can use a hash table. Since inserting and searching in a hash table is O(1), you can do this in a single loop, yielding O(N) time complexity.

However, your question is about "limited input data". So if you limit your input data to sorted arrays, you can reduce the complexity to O(N). To be precise, if you know that the array is sorted (this is your limitation), than a single loop that compares every element to its successor(s) will find the duplicates.

If the array is not sorted, you need an outer loop over all elements but the last, and an inner loop over all the remaining elements. If the array is sorted, you don't need the inner loop, just compare to the next element. That is the "reduction" of the algorithm, resulting in a "reduction" of O(N^2) to O(N).

Answer 2

one way is to sort and then remove duplicates, but you need an additional memory

Pseudocode:

remDups(arr,arr2)

   Sort(arr); // O(nlogn)
   arr2[0] = arr[0];
   j=1;
   foreach(i+1 to arr.len : i++) //O(n)
   {
      if(arr[i-1] == arr[i]) continue;
      arr1[j++] = arr[i];
   }

O(nlogn)

You can use, HashTablemethod