Greater time complexity of a recursive nested loop algorithm

Question

I have a recursive algorithm with two nested loops. I am trying to understand what the complexity of Big-O time will be.

public Set<Person> getDistinctCombinedPersons(Collection<Person> persons) {
  return permutatePersons(new ArrayList(persons), new HashSet<>(persons));
}

---

private Set<Person> permutatePersons(List<Person> personList, Set<Person> personSet) {
  if(personList.isEmpty() {
    return personSet;
  }

  Set<Person> deepCopyPersonSet = new HashSet<>(personSet);

  for(Person lPerson : personList) {
    for(Person sPerson : deepCopyPersonSet) {
      Person uniquePerson = CombinePeople.combine(lPerson, sPerson);
      personSet.add(uniquePerson);
    }
  }

  personList.remove(personList.size()-1);

  return permutatePersons(personList, personSet);
}

Answer 1

Assuming that you call permutatePersonsthe list length N, the following recursion is used:

T(N) = T(N-1) + O(N^2)

This is because at each recursive step you call a function with a list of length N-1 (where N is the current length), and also perform calculations of full complexity O (N ^ 2) (outer loop O (N) -just traversing list and inner cycle crossing the hash map in O (N) -O (1) for each element and the common element N, therefore the nested loops are generally O (N ^ 2)).

You can easily see:

T(N) = T(N-1) + O(N^2) = T(N-2) + O(N^2) + O((N-1)^2) =...

= O(n(n+1)(2n+1)/6) = O(n^3)

Answer 2

, -O n ^ 2:

  for(Person lPerson : personList) {
    for(Person sPerson : deepCopyPersonSet) {
      Person uniquePerson = CombinePeople.combine(lPerson, sPerson);
      personSet.add(uniquePerson);
    }
  }

.

O of n, .

: n * n^2 O n ^ 3

Answer 3

Since you have two nested loops, you have run-time complexity O(m*n). This is because, for n- Personin deepCopyPersonSetyou repeat magain. nin this example, this is the number Personin personList.

Your code is basically:

for(int i = 0, i < m, i++)
  for(int j = 0, j < n, j++)
    //your code 

For each iteration m, we have n code iterations