What is Polynominal Time ?

A Polynomial time algorithm is the type of algorithm whose execution time grows at most polynomially with the Input Size. It is denoted by (0 ( n^k ) ).The time is obtained when the search over all subsets of a set of size "k" is performed.

Polynomial time is a critical concept in the field of computer science, particularly in the study of algorithms and computational complexity. It refers to the amount of time it takes for an algorithm to solve a problem, relative to the size of the problem instance, expressed as a polynomial function of the problem's size.

In simpler terms, an algorithm is said to run in polynomial time if the time it takes to solve a problem instance grows no faster than a polynomial function of the size of the input. This means that as the size of the input increases, the time taken by the algorithm increases at a manageable rate, allowing it to scale efficiently.

The significance of polynomial time lies in its relationship to the efficiency of algorithms. Algorithms that run in polynomial time are generally considered efficient, as their time complexity doesn't explode as the size of the input grows. This makes them suitable for solving real-world problems efficiently, even for large input sizes.

Common examples of algorithms with polynomial time complexity include algorithms for sorting (such as bubble sort, insertion sort, and merge sort), searching (such as binary search), and graph traversal (such as breadth-first search and depth-first search).

In contrast, algorithms with exponential or factorial time complexity are generally considered inefficient, as their running time grows exponentially or factorially with the size of the input. Problems that can only be solved by algorithms with exponential or factorial time complexity are often considered intractable for large input sizes.

The study of polynomial time algorithms and problems plays a crucial role in understanding the capabilities and limitations of computational systems. It forms the foundation of complexity theory, which seeks to classify problems based on their inherent difficulty and the resources required to solve them. Polynomial time algorithms represent a class of problems that are efficiently solvable, making them a fundamental building block in the design and analysis of algorithms.

For an Example if we consider brute - force methos and consider a graph with n points on its, to find the number of the independent points will have to check the each of the node with all other nodes to whether they make an edge or not if then make an edge then they are considered separate. this calculation takes about the multiple of n as the number of input or the number of nodes in a graph increases. hence this is dependent on the number of the input with polynomial multiplication.