Big-O time complexity of recursive algorithm with nested for loops

Question

I have a recursive algorithm with two nested for loops. I'm trying to figure out what the Big-O time complexity 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);
}

(By the way, "deep copy" doesn't mean what you think it does.) — ruakh
– ruakh, Commented Nov 9, 2017 at 23:05
I'm wondering if I can just remove the outer for loop somehow? — Grammin
– Grammin, Commented Nov 10, 2017 at 0:05

game0ver · Accepted Answer · 2017-11-09 23:57:57Z

4

Assuming that you call permutatePersons with a list of length N the following recursion applies:

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

That's because in every recursive step you call function with list of length N-1 (where N the current length) and also you do computations of total complexity O(N^2) (outer loop O(N) -just traversing list and inner loop traversing the hash map in O(N) -O(1) for each element and total N element, So the nested loops are overall 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)

answered Nov 9, 2017 at 23:57

game0ver

1,29010 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Grammin Over a year ago

Thank you for the excellent answer. I'm now wonder if I take out the outer for loop is the algorithm still doing the same thing?

game0ver Over a year ago

In terms of complexity no it will be reduced in O(N^2) due to the recursion now will be: T(N)= T(N-1) + O(N).

Grammin Over a year ago

Yea I'm wondering though if my algorithm is the exact same if I remove the outer for loop just less complex

game0ver Over a year ago

No if I understand correctly what you're trying to do-to generate all 2-combinations of persons you need two loops-O(N^2) and O(N^3) overall...

nasxlf · Accepted Answer · 2017-11-09 23:54:56Z

0

Because you have two nested loops you have the runtime complexity of O(m*n). It's because for n-Persons in deepCopyPersonSet you iterate m times. n in this example is the quantity of Persons in personList.

Your code is basically:

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

For every iteration of m, we have n iterations of code

answered Nov 9, 2017 at 23:54

nasxlf

458 bronze badges

1 Comment

Grammin Over a year ago

I also have the recursive call in there too

luckydog32 · Accepted Answer · 2017-11-10 00:12:31Z

0

Looks like it would be a big-O of n^2 for the nested loop:

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

You have to iterate over the each element for each element in the set.

And then the recursive call has a big O of n since it will call your method once for each element in the set.

Combining the two: n * n^2 will result in a big O of n^3

edited Nov 10, 2017 at 0:12

answered Nov 9, 2017 at 23:54

luckydog32

9096 silver badges13 bronze badges

4 Comments

jhpratt Over a year ago

What effect does the recursion have?

luckydog32 Over a year ago

@jhpratt I don't this the method is using any recursion unless I'm missing something. Do you mean iteration?

jhpratt Over a year ago

Nope, the last line is a recursive call.

Grammin Over a year ago

I also have the recursive call in there too

Collectives™ on Stack Overflow

Big-O time complexity of recursive algorithm with nested for loops

3 Answers 3

4 Comments

1 Comment

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

1 Comment

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related