The pseudocode for the independent set problem is given below. Which of the following gives the time complexity for it?
Independent (G = (V, E))
{
temp=true
for every {u, v} in the subset
{
check if they have any edge between them
if edge exists, then set temp as false and break
}
If temp is true
correct result
else
incorrect
}
Independent (G = (V, E))
{
temp=true
for every {u, v} in the subset
{
check if they have any edge between them
if edge exists, then set temp as false and break
}
If temp is true
correct result
else
incorrect
}
A. O(V + E)
B. O(V)
C. O(V log V)
D. O(V log E)
Answer: Option A
Join The Discussion