We can solve Set Cover Problem by forming all the possible sets combination and verifying whether it is the minimum solution. Now we can have at most 2^n such sets combination where 'n' is the number of Set.
So, the complexity of this approach should be O(2^n). However, Wikipedia says 'the complexity of Set Cover Problem is m^n where m is the size of the universe and n is the number of sets in the collection'.
Can somebody explain how complexity is O(m^n) and not O(2^n)?
Thanks in Advance.
You're almost right; the complexity of the brute force algorithm is O(m 2^n) up to model-dependent log factors, because manipulating those sets isn't free. O(m^n) probably comes from the idea that, for each of m elements, we choose one of at most n sets for it to be covered by. The most charitable possible explanation that I can offer is that the primary source stated a bound of O(m^k) for instances of set cover where each element belongs to at most k sets, a special case considered in the context of approximation algorithms (there's a polynomial-time k-approximation).
Seems rather simple to me.
Problem visualization:
def Set Cover = what is the minimum paths required to contain all nodes.
Brute force solution:
a = find number of unique nodes in universe
b = find all path permutations as list
c = find b elements where number of unique nodes equals a
d = order c by path count and pick first
Finding all permutations is not O(m^n), but O(n!), and this would be vastly inefficient if universe if big. However you do not need all path permutations, you could just find path permutations up to size x, where x enumerates from 1 to a. However I assume you get the idea.
