Design and Analysis of Algorithms20795 marksTractable and Intractable Problems, Concept of Polynomial Ti
Define tractable and intractable problem. Illustrate vertex cover problem with an example.
Define tractable and intractable problem. Illustrate vertex cover problem with an example. [5]
--- A problem is said to be tractable if it can be solved in polynomial time, i.e., its time complexity is O(n^k) for some constant k. These problems are considered efficiently solvable in practice. Examples: Sorting (O(n log n)), Binary Search (O(log n)), Shortest Path (Dijkstra's O(V^2)) A prob...