Q151: Asymptotic notation

Question 151: Which of the following is true?

1. O(n²) = n
2. O(n²) = n³
3. O(n²) = n² log(n)
4. All of the above

Solution: The correct answer is option 1. Both n³ and n² log(n) are asymptotically larger than n² , since we can’t find any real positive valued of n₀ & c to satisfy the following inequality.

O(g(n)) = f(n) : 0 <= f(n) <= c g(n) for all n > n₀

Q63: Are NP-hard problems solvable?

Question 63: Can NP-hard problems never be solved on a computer machine?

1. No, they are unsolvable.
2. They can be solved but they are classified so because they take such a lot of time on current machines that practically computers are useless for all but very small instances of problems.
3. They can be solved but they are classified so because they take such a lot of time on current machines that practically computers are useless for all but very large instances of problems.
4. There are no known solutions for NP-hard problems

Solution: They can be solved but there are no known polynomial time algorithms for them. The correct answer is option 2.

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.