2
$\begingroup$

I'm having a difficult time understanding time complexities of algorithm. I know that a polynomial time is of the form O(n^m) where m is a constant. Consider the following case where A is a list of elements:

Foo(A)
for each element a in A:
    for each element b in A-a:
        Polynomial-Time-Algorithm-Bar(A, a, b)

If n is the size of A,

1) Am I right in understanding that Foo(A) is also a polynomial time algorithm , because the function Polynomial-Time-Algorithm-Bar is called (n-1)*n times ?

2) When would an algorithm making calls to another polynomial time algorithm become exponential. I understand that if it has a running time of O(n^m) and m is variable and n is constant, then it would be exponential. Can you give me an example of such a case in the above example?

$\endgroup$
3
$\begingroup$

I assume $n$ is the number of entries in array/set A.

  1. Yes, since polynomials are closed against multiplication; specifically, $n(n-1) \cdot p(n)$ is always polynomially bounded as long as $p(n)$ is polynomially bounded.

  2. As a consequence, the only way to achieve exponential running-time by calling a polynomial-time algorithm with parts of the original input is to call it exponentially often.

    Example:

    Foo(A)
      if |A| >= 2
        a = A[0]
        b = A[1]
        Polynomial-Time-Algorithm-Bar(A, a, b)
        Foo(A - a)
        Foo(A - b)
    

    The number of calls to PTA-Bar is given by

    $\qquad\begin{align*} C(0) &= 0,\\ C(1) &= 0,\\ C(n) &= 2C(n-1) + 1, \qquad n \geq 2, \end{align*}$

    which solves to $C(n) = 2^{n-1} - 1$ for $n \geq 1$. Ergo, the running time of Foo is in $\Omega\bigl( 2^n \cdot p(n) \bigr)$ if PTA-Bar takes time $p(n)$.

$\endgroup$
  • $\begingroup$ Calling it on inputs of size 2^(n^(Ω(1))) is another "way to achieve exponential running-time by calling a polynomial-time algorithm". ​ ​ $\endgroup$ – user12859 Oct 27 '16 at 2:12
  • $\begingroup$ @RickyDemer Add an answer? $\endgroup$ – Raphael Oct 27 '16 at 9:34
  • $\begingroup$ @RickyDemer So it doesn't have to be a recursive algorithm to be an exponential? It would be great if you can elaborate with an answer. $\endgroup$ – MadhavanRP Oct 27 '16 at 18:16
  • $\begingroup$ @MadhavanRP You can always replace recursion with loops; I just found this example approachable and realistic. (Consider, for instance, for i = 1 .. 2^n do PTA-Bar(...) end -- trivial.) $\endgroup$ – Raphael Oct 27 '16 at 18:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.