Q17: Time complexity to find independent set

Question #17: What is the time complexity of the following algorithm?

Here, a graph of n nodes is assumed and the problem is to find an independent set of size k. The algorithm enumerates all k sized subsets and then checks if any one of them satisfies the independent set property. Independent set is a set of vertices such that no two vertices in the set have an edge between them.

Options:

1. O(n^k)
2. O(kⁿ)
3. O(nⁿ)
4. O(k^k)

 

Solution:

There are C(n,k) total sets of size k from n vertices. And each of this set is checked, so complexity is of the order O(n^k). Hence, the correct answer is option 1.