Please explain in detail1Thanks Circle T true or F false for

Please explain in detail!!!!!!!!!!!!1Thanks

Circle T (true) or F (false) for each of the following statements to indicate whether the statement is true or false (Note that you will get -1 mark for each incorrect answer). For all positive integers n, an O(n)-time algorithm always runs faster than an 0(2n)-time algorithm. A greedy algorithm does not always find an optimal solution. Kruskal\'s minimum spanning tree algorithm works correctly even when the input graph contains edges of negative weights. Although we cannot solve SUBSET SUM in polynomial time by a greedy algorithm, we can solve it in polynomial time by dynamic programming. No NP-complete problem can be solved in polynomial time unless the Vertex Cover problem admits a polynomial-time algorithm. There is a linear-time algorithm to find a vertex cover whose size is at most twice the size of an optimal one. It is NP complete to determine whether a graph contains a vertex cover of size 1000.

Solution

a.) True. Since the algorithm with O(n) doesn\'t expands exponentialy as compared to O(2ⁿ) for all positive n. Consider n =1,2,3.. and so on it shows that O(2ⁿ) expands widely.

b.) True. Since it is greedy it considers that moment only but the optimal solution is for whole situation. A greedy algorithm always choose a solution which is best at that point. So it won\'t always gives optimal solution.

c.) True. Kruskal works fine with negative weights as if we add a big positive constant to all the edges of the graph with negative weights, making all the edges positive.

d.) True. It can be solved in polinomial time with dynamic programing.