0

For last couple of weeks i have been coding various programs in which i have to use the nested for loops. This raises the complexity of my code to O(n^2). Is there a way i can use the parallel algorithms to reduce this complexity. I read something about the prefix sum algorithms, but there is no sufficient explanation available on that. For example a code is given below. Any help please ??

for(i=0;i<n;i++)
{
  for(j=0;j<m;j++)
  {
    if(array1[i]==array2[j];
    System.out.println(array1[i]);
  }
}
Magnum
  • 83
  • 1
  • 5
  • 1
    Possible duplicate of [How do I get the intersection between two arrays as a new array?](http://stackoverflow.com/questions/13270491/how-do-i-get-the-intersection-between-two-arrays-as-a-new-array) – Paul Hankin Apr 22 '17 at 14:58
  • Re: "Is there a way i can use the parallel algorithms to reduce this complexity": Never, unless you have an infinitely large computer. If you have any finite number of processor cores -- say, *k* -- then even in the very best case, you can only improve an Θ(f(n)) algorithm to Θ(f(n)/k) by making it parallel, which is still Θ(f(n)). – ruakh Apr 22 '17 at 15:24

1 Answers1

0

What this code is doing doesn't require a nested loop, and can be done in O(n) or O(nlogn) by using one of the two methods:

  1. Populate a set (tree/hash table based) of one array, then iterate the second array and for each element, check if it exists in the set (Note: This solution does not handle duplicate, for duplicates, use a multiset or a map, where keys are elements from first array and values are the number of occurances).
  2. Sort the arrays, and iterate them together. After arrays are sorted - finding the output can be done in linear time.
amit
  • 175,853
  • 27
  • 231
  • 333
  • These are better approaches overall, but please note that: (1) sorting `array1` will affect the order in which elements are output; (2) if both arrays can contain duplicates, then you can never get better than O(mn) worst-case time (meaning O(n^2) if the arrays are the same size), because the worst-case number of calls to `System.out.println` is O(mn). So the OP's question can't be properly answered without more information about his/her requirements. – ruakh Apr 22 '17 at 15:30