What's Time Complexity of This Algorithm for Finding All Combinations

What's time complexity of this algorithm for finding all combinations?

Since you are using lists, push_back and pop_back are O(1) operations. Also, you end up generating a valid combination exactly once. Thus, the complexity is O(n choose k).

Complexity when generating all combinations

First, there is nothing wrong with using O(n! / (n-k)!k!) - or any other function f(n) as O(f(n)), but I believe you are looking for a simpler solution that still holds the same set.

If you are willing to look at the size of the subset k as constant, then for k <= n - k:

n! / ((n - k)! k!) = ((n - k + 1) (n - k + 2) (n - k + 3) ... n ) / k! 

But the above is actually (n ^ k + O(n ^ (k - 1))) / k!, which is in O(n ^ k)

Similarly, if n - k < k, you get O(n ^ (n - k))

Which gives us O(n ^ min{k, n - k})

Algorithm to find all combination from an array of objects

What is the best algorithm to find all possible combination for this problem?

In the worst case, where you have n >= 6 athletes, each weighing so little that the limit doesn't matter, and each able to play all roles, the number of teams grows very, very quickly, even if you don't want to multiply-count the teams that have the same set of players assigned to different roles.

The exact number in this case is "n choose 6" or:

n * (n - 1) * (n - 2) * (n - 3) * (n - 4) * (n - 5) / 720

This is an O(n⁶) problem. This is going to be slow no matter what if n is larger than, like, 30. Once n > 123, the quantity won't fit in an unsigned 32-bit integer anymore.

If the team size can vary, then the problem is O(n^k), where k is the team size. This is no longer polynomial; in fact, it's harder than NP-Complete. It would be able to enumerate solutions to the Knapsack Problem, which is ♯P complete.^[1]

Thus, this is an engineering problem more than it is an algorithms problem.

Right now I find all combination iterating through the list of athletes, all of its roles and removing all combinations that overpass a limit.

This is pretty much what I would do, only you can make it somewhat more efficient by pruning partial teams as early as possible. Here are some ideas I had:

1. Sort the list of athletes by weight so that when you go over the weight limit, you can stop looking at the later athletes in the list.
2. Keep track of how many roles have a possible athlete to fulfill them, given the partial team. When you reach the fifth member, you know the athlete must have a role in one of the shorthanded roles.
   
   1. For example, if you have a team of four athletes so far with no median players, you must only consider median players for the next two.
   2. To make this easier, create (sorted) auxiliary lists for each role that contain pointers to the players that can have that role.

Classification and complexity of generating all possible combinations: P, NP, NP-Complete or NP-Hard

P, NP, NP-complete, and NP-hard are all classes of decision problems, none of which contain problems that involve non-binary output (such as this enumeration problem).

Often people refer colloquially to problems in FNP as being in NP. This problem is not in FNP either because the length of the output string for the relation must be bounded by some polynomial function of the input length. It might be FNP-hard, but we're getting into the weeds that even a graduate CS education doesn't cover. Worth asking on the CS Stack Exchange if you care enough.

Time complexity of this combination algorithms

Thanks @Michael Foukarakis for pointing the missing K.

Base case: T(n, 0) = 1
Recurion : T(n, k) = T(n-1, k-1) + T(n-2, k-1) + T(n-3, k-1) + .. + T(0, k-1) + 1
                   = n * T(n-1, k-1) + 1

Expanding it as below

T(n, k) = n * T(n-1, k-1) + 1
        = n * (n-1) * T(n-2, k-2) + 1 + 1
        = n * (n-1) * T(n-2, k-2) + 2
        = n * (n-1) * (n-2) * T(n-3, k-3) + 3

        ...

         = n * (n-1) * (n-2) * ..(n-k) T(n-k, k-k) + k
         = n * (n-1) * (n-2) * ..(n-k) (1) + k
         = O(n^k)  (As it is a k th order polynomial)

Overall we can say O(n^k) runtime.

Isn't the time complexity for combinations in Python O(n)?

r=1 and r=n rather are (almost) best cases (actually r=0 is the lower extreme), not worst cases. Worst case, at least for number of combinations, is r=n/2. So if you do want to express the complexity in terms of just n, it's O(nC(n/2)) or O(n × nC(n/2)), depending on what you do with the tuples.

Time complexity of generating all possible permutations using backtracking (comparison of 2 solutions)

In both algorithms, the recursive function is entered once for every prefix of a permutation of {1, …, n}. In the first algorithm, we can imagine the work done by each iteration of the for loop being accounted for inside the recursive call, since there will be a recursive call for every iteration. So the total amount of work is proportional to the number of possible prefixes. Since they are not proper prefixes, this includes all the permutations; so there are more than n! prefixes in all. In fact, the number of prefixes of length n-1 is also n!, so there are more than 2(n!) prefixes, but the remaining terms drop off pretty rapidly. It turns out that there are asymptotically e(n!) prefixes, where e is Euler's constant, approximately 2.71828. So that's O(n!), since we can ignore constant factors.

Now what about the second algorithm? We have the same number of recursive calls but each recursive call which does not correspond to a complete permutation requires a scan over the chosen array, which has n elements. That adds n × (e - 1) × n!. In effect, it changes the asymptote to O((n+1)!), which is bigger than O(n!). But not as much as O(nⁿ).

---

Related Topics