Nested Polynomial-Time functions

algorithm, complexity-theory, polynomial-math

Solution

Well, if we treat this as a "dirty trick" question:

def g(a):
    b = 0
    for i in range(a * 2):
        b += 1
    return b

def f(x):
    a = 1
    for i in range(x):
        a = g(a)

g(a) runs in O(a), f(x) runs in O(x) times before the call to `g`, but overall it is `O(2 ^ n)`.

Problem

If I run a polynomial-time subroutine a polynomial number of times, what are some examples of a way that this is done in exponential time? "show that a polynomial number of calls to polynomial time subroutines may result in an exponential-time algorithm." - a problem of a HW

Original source