What is the Time Complexity of this Function in Scheme?

Question

I am trying to find the time complexity of this function in Theta notation. Now, n is a positive integer, and lst is a list with 2 numbers.

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

As you know, the time complexity of append is Θ(n) where n is the overall size of the lists. I tried to see what happens if I treat append and accumulate as Θ(1) functions, then I get:

T(n) = 2T(n-1) + Θ(1) which is --> Θ(2^n)

Does this mean that the actual time complexity of this thing in Theta notation is way bigger than Θ(2^n)?

I'm not even sure that I'm right with this assumption alone, and anyways, I'm clueless on what to do if I need to take into consideration both accumulate and append...

I've wasted hours on this one, and I really don't understand why I can't figure it out on my own... Any help would be gladly appreciated.

btw, here is the code of accumulate:

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

Answer 1

It sounds plausible, if you take a look at the output.

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

For every element of lst 2^n elements are created which is l*2^n. The algorithm could only be worse.

And obviously it is bad. The function accumulate is not tail recursive and func therefore either not. A 2^n non tail recursive function is quite useless.