Polynomial Running Time

Polynomial Running Time describes an algorithm which, when the input size doubles, it’s Running Time only decreases by a factor of some constant $C$.

This may also be referred to commonly as fast or quick Running Time.

---

Example:

int[] array = new int[]{0, 1, 2, ...};
 
for (int i = 0; i < array.length; i++) 
	for (jnt j = 0; j < array.length; j++) 
		if (condition(array[i], array[j]))
			doThing();	

Here the running time is $O(N^2)$ which is a polynomial with constant $C$.

---

Relations:

For two algorithms $X$ and $Y$, the following can be established between them (comparing Running Time):

• If $X{\le }_{p}Y$ and $Y$ can be solved in polynomial Running Time, then $X$ can also be solved in polynomial Running Time.
• If $X{\le }_{p}Y$ and $X$ can’t be solved in polynomial Running Time, then $Y$ cannot also be solved in polynomial Running Time.
• If $X{\le }_{p}Y$ and $Y{\le }_{p}X$, described with notation $X{\equiv }_{p}Y$, $X$ can be solved in polynomial Running Time if $Y$ can be.