Nested Polynomial-Time functions

Question

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

Answer 1

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).