34.1-5

Mostre que um algoritmo que efetua no máximo um número constante de chamadas a sub-rotinas de tempo polinomial é executado em tempo polinomial, mas que um número polinomial de chamadas a sub-rotinas de tempo polinomial pode resultar em um algoritmo de tempo exponencial.

O problema está nos tamanhos das entradas para as sub-rotinas. Se as chamadas são em número constante, não há como os tamanhos das entradas crescerem além de um fator constante vezes o tamanho da entrada do próprio algoritmo, resultando em tempo polinomial.

Por outro lado, mesmo um número linear de chamadas a sub-rotinas lineares pode resultar em tempo exponencial, como mostra o exemplo abaixo, onde os argumentos exp e stri são strings.

Alg ( exp ) 
    s <- esp.size
    for i <- 1 to s do
        exp <- Dobra(exp)

Dobra (stri)
    return stri + stri   // + significa concatenação de strings

O algoritmo Alg gasta tempo Ω(n . 2n), onde n é o tamanho da entrada.