Please figure out time complexity using Big O Notation - O(n!) of the following steps used to create a straightforward algorithm: The straightforward algorithm we are proposing is an exhaustive search. The algorithm should count the number of edges in G, we call that number m. First, we check the delta set of vertex sets that contain only one element to see if they cover all edges in G. (n number of checks for sets δA1, δA2,... δAn). If a set satisfying the conditions is not found, we move to placing δA1 next to one other set, and check the union of the sets to see if there is a combination of two sets that satisfies the question. We repeat with δA2, δA3,... δAn without repeating combinations. For example, when checking δA2, we skip over δA1 since we have checked δA1 δA2 in the previous step. If a satisfactory set is not found, we continue searching with increasing the number of sets being combined. Since the question is asking for a vertex set of V in G so that each edge of G has at least one end in V, the maximum number of vertices in V should be n+1/2. The algorithm should return a combination of vertices that satisfies the condition of the question before it finishes checking for combinations of n+1/2 vertices (rounded down).

Related questions

Question

Please figure out time complexity using Big O Notation - O(n!) of the following steps used to create a straightforward algorithm:

The straightforward algorithm we are proposing is an exhaustive search. The algorithm should count the number of edges in G, we call that number m.

First, we check the delta set of vertex sets that contain only one element to see if they cover all edges in G. (n number of checks for sets δA1, δA2,... δAn).
If a set satisfying the conditions is not found, we move to placing δA1 next to one other set, and check the union of the sets to see if there is a combination of two sets that satisfies the question.
We repeat with δA2, δA3,... δAn without repeating combinations. For example, when checking δA2, we skip over δA1 since we have checked δA1 δA2 in the previous step.
If a satisfactory set is not found, we continue searching with increasing the number of sets being combined. Since the question is asking for a vertex set of V in G so that each edge of G has at least one end in V, the maximum number of vertices in V should be n+1/2.
The algorithm should return a combination of vertices that satisfies the condition of the question before it finishes checking for combinations of n+1/2 vertices (rounded down).

Expert Solution

Step by step

Solved in 3 steps