Edit Question - KnowledgeHub

Title Body

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

Tags (comma-separated) Cancel