Hello guys,

Which are the asymptotic complexity of this functions?

Code:

Function(T) /* T is a Binary Search Tree */
L.Head = NULL /* L is a new empty list of integers */
Function2(T.root, L, 0)
return L
Function2(v, L, depth)
if (v == NULL) return
if (depth == 3)
AddToTail(L, v.info)
else
AddToHead(L, v.info)
Function2(v.left, L, depth+1)
Function2(v.right, L, depth+1)

Hypothesis:

AddToTail does a number of operations proportional at current list.

AddToHead does a constant number of operation.

This is my exercise.

For me the complexity of Function(T) is the same of Ric_Func.

Instead, Function2?

I think that for the best case (when the tree's depth is < of 3) the complecity is n, 'cause does nothing but visit the tree.

For the worst case (when the tree's depth is > of 3) then the complexity increases until to n^2. 'cause the code have to scan the n elements of list. It's correct?

And for the middle case? always n^2?