¿Cuál es la complejidad temporal de esta función en el esquema?

Question

Estoy tratando de encontrar la complejidad de tiempo de esta función en la notación Theta. Ahora, n es un entero positivo, y lst es una lista con 2 números.

(define (func n lst) 
    (if (= n 0) lst 
     (accumulate append null 
        (map (lambda (x) 
         (func (- n 1) (list x x))) 
         lst)))) 

Como saben, la complejidad de tiempo de agregación es Θ (n), donde n es el tamaño total de las listas. Traté de ver qué pasa si trato agregar y acumular como Θ (1) funciones, entonces obtengo:

T (n) = 2T (n-1) + Θ (1) que es -> Θ (1) 2^n)

¿Esto significa que la complejidad del tiempo real de esta cosa en la notación Theta es mucho mayor que Θ (2^n)?

Ni siquiera estoy seguro de que estoy en lo cierto con este supuesto solo, y de todos modos, no tengo ni idea de qué hacer si necesito tomar en consideración tanto se acumulan y añadir ...

I He perdido horas en esto, y realmente no entiendo por qué no puedo resolverlo por mi cuenta ... Cualquier ayuda sería gratamente apreciada.

por cierto, aquí está el código de acumular:

(define (accumulate op init lst) 
    (if (null? lst) 
     init 
      (op (car lst) 
      (accumulate op init (cdr lst))))) 

Answer 1

Suena convincente, si se echa un vistazo a la salida.

(func 3 (list 1 2 3)) 
=> (1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3) 

Para cada elemento de lst 2^n se crean elementos que es l * 2^n. El algoritmo solo podría ser peor.

Y, obviamente, es malo. La función acumulada no es recursiva de la cola y, por lo tanto, func tampoco. Una función recursiva sin cola 2^n es bastante inútil.