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?