Finding the order of growth of a procedure that calls many procedures

Question

This code creates a balanced binary search tree that is an intersection of two balanced binary search trees.

(define (intersection-tree t1 t2)
    (list->tree (intersection-set (tree->list-2 t1) (tree->list-2 t2))))

• tree->list-2 flattens a tree into an ordered set. It takes Theta(N).
• intersection-settakes two sets an creates a new set with the intersection of the two input sets. It takes Theta(N).
• list->tree turns the newly created set into a balanced binary search tree. Takes Theta(N).

That is, I have a procedure that calls 4 procedures that takes Theta(N) (list->tree, intersection-set, two tree->lists). My guess is all of these takes 4N. Ignore constant factors it becomes Theta(N). Is it correct to say the intersection-tree procedure takes Theta(N)?

Answer 1

Your guess is correct, since in your function each subtask is executed only once, with Theta(N), for a constant number of times, the intersection-tree procedure takes Theta(N).