Time complexity to generate all pairs in an array

Question

Given an array of numbers, generate all unique pairs.

For example, given [ 1, 2, 3, 4, 5 ] the unique number pair would be:

(1, 2), (1, 3), (1, 4), (1, 5)  (2, 3), (2, 4), (2, 5)  (3, 4), (3, 5)  (4, 5) 

My solution is as follows:

int[] numbers = new int[] { 1, 2, 3, 4, 5 }; HashSet<Pair> pairs = new HashSet<Pair>();  for(int i = 0; i < numbers.Length; i++) {     for(int j = i + 1, j < numbers.Length; j++)     {         pairs.Add(new Pair(numbers[i], numbers[j]));     } } 

I think the time complexity for this looks like O(n² - 1) subtracting 1 because iteration of j is always 1 shorter than i

Having done a bit of research into this kind of problem, I can't find any definitive answers as to whether this can be done faster. Are there any better solutions than O(n² - 1)?

Answer 1

One of the way to think about "is there faster way to solve the problem" is to look to the size of the output for some specific format (which you consider "probably the biggest/most difficult to solve").

If the output is O(n^2), then you cannot solve the problem faster than in O(n^2), because you have to spend at least O(1) for each output.

You can see the pattern there, if you have 5 numbers in format [1, 2, 3, 4, 5], unique pairs take

4 pairs in first row 3 pairs in second row 2 pairs... 1 pair 

because they look like

(1, 2), (1, 3), (1, 4), (1, 5)  (2, 3), (2, 4), (2, 5)  (3, 4), (3, 5)  (4, 5) 

If you have 20 variables in array (in format [1, 2, 3,... 18, 19, 20]), it will be as following:

19 pairs 18 pairs ... 2 pairs 1 pair 

Therefore the output size is (n-1) + (n-2) + (n-3) ... + 3 + 2 + 1. You have to sum it (look to how to sum the series) and the result is O(n^2)

What was proved?

That the worst case scenario is AT LEAST O(n^2).

Also note, that at this moment, we dont know real worst-case complexity - alghorithm can be even slower (we just find that some input takes O(n^2)). We know for sure that at least these data takes O(n^2). It can be faster or slower for different input.

---

Conlusion: We have proof, that the algorithm takes at least O(n^2) time (as worst-case scenario), you created algorithm that is running in maximum of O(n^2) time (as described in spyc post) = You have optimal algorithm.

---

Extra info to OP's solution: Detecting collisions with HashSet is only "pseudoConstant" and only for small numbers and "some luck". It takes O(n) for big amount of numbers. So you can end up in n^2 output and each of them takes up to n to process which leads to n^3 complexity.

You can solve it with preprocessing the task:

1) Sort it - it takes only n log n, so does not affect n^2 anyway

2) Remove numbers that repeats more than twice [1, 3, 3, 3, 5] -> [1, 3, 3, 5], it is O(n)

3)Then use your algorithm with this update:

3.1) In beginning of for i cycle: if (number[i] == number[i-1]) continue;

3.2) In beginning of for j cycle: Remember last pair. When adding new pair, look to the last pair and check if it is same or not. If so - continue;

Example:

Input: [1, 3, 3, 5]  1)i=0, j=1, number[0]=1, number[1]=3 -> add (1, 3) 2)i=0, j=2, number[0]=1, number[2]=3 -> same as last pair, use continue 3)i=0, j=3, number[0]=1, number[3]=5 -> add (1, 5) 4)i=1, j=2, number[1]=3, number[2]=3 -> add (3, 3) 5)i=1, j=3, number[1]=3, number[3]=5 -> add (3, 5) 6)i=2, before go to j-cycle, check number[i] === number[i-1] It is true, use continue 

Answer 2

It goes as follows:

first for loop - O(n)     second for loop - O(n-1)   

Optimal Time complexity :

• Even though that one iteration is negligible, and you should calculate the time complexity for worst case scenario, which is

You can also use binomial coefficient for permutations, to get number of permutations of a certain string. For example:

If you have 6 digits {0,1,2,3,4,5} (n=6), and you want to know how many different permutations you can make, i.e : (3,5) , (5,3) etc... then the (k=2, two digits in each group), the amount of permutations will be:

different permutations, do note though that in this case (3,5) , (5,3) are counted individually, so the order of it all matters. If you want (5,3) and (3,5) to be counted as one combination then the equation goes as follows:

---

Example implementation, calculating permutations!

static long factorial(long x) // calcs the factorial TimeCmplx = O(n) {     if (x == 1)         return x;     return x * factorial(x - 1); }  static long permutations(long n , long k) //Check that (n , k) >= 0 {                 // Permutations , n!/(n-k)!     return factorial(n) / factorial(n - k); }