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)))))
Edit
Report