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