1. ## Asymptotic complexity help

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)
else
Function2(v.left, L, depth+1)
Function2(v.right, L, depth+1)```

Hypothesis:
AddToTail does a number of operations proportional at current list.
This is my exercise.

For me the complexity of Function(T) is the same of Ric_Func.
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?

2. My guess is n^2 is not correct. But, it is a guess based on my poor memory of this subject from over an decade ago.

Tim S.

3. Originally Posted by stahta01
My guess is n^2 is not correct. But, it is a guess based on my poor memory of this subject from over an decade ago.

Tim S.

4. Why are you saying <3 when your test is ==3 ?

For arbitrarily large trees, your single special value is insignificant. You may as well assume that AddToHead always happens.

5. Originally Posted by Salem
Why are you saying <3 when your test is ==3 ?

For arbitrarily large trees, your single special value is insignificant. You may as well assume that AddToHead always happens.
Because < 3 and > 3 are the cases where "AddToHead" function doesn't run. So, it's like the code does a simply visit of tree, therefore its complexity is n, right?
When, instead, the depth is = 3, the code runs AddToHead (an function with n complexity) and this not affects its complexity?

6. I think you've got head and tail mixed up.

7. Originally Posted by Salem
For arbitrarily large trees, your single special value is insignificant. You may as well assume that AddToHead always happens.
Maybe not? If the tree is deep then each time a 3rd-level node is processed it is proportionately more expensive. So although there are only a handful of 3rd level nodes they get more expensive as you go along.

Consider a complete 20-level tree (~ one million nodes)
Code:
```.               1
2               3
4       5       6       7
8   9   10 11   12 13   14 15
a b c d e f g h i j k l m n o p

a,b,c,etc all have 65535 nodes (incl. themselves)
There are two such subtrees under each level 3 node
65535 * 2 = 131070 plus the node itself = 131071

node | list length
8     3            =      3
9     3 + 131071   = 131074
10     4 + 131071*2 = 262146
11     4 + 131071*3 = 393217
12     6 + 131071*4 = 524290
13     6 + 131071*5 = 655361
14     7 + 131071*6 = 786433
15     8 + 131071*7 = 917505
=======
3670029 operations just to add the 3rd level nodes
+ (1048575-8) ops for the other nodes
========
4718596```

8. Originally Posted by Salem
I think you've got head and tail mixed up.
you are right, but my reasoning remains

Originally Posted by john.c
Maybe not? If the tree is deep then each time a 3rd-level node is processed it is proportionately more expensive. So although there are only a handful of 3rd level nodes they get more expensive as you go along.

Consider a complete 20-level tree (~ one million nodes)
Code:
```.               1
2               3
4       5       6       7
8   9   10 11   12 13   14 15
a b c d e f g h i j k l m n o p

a,b,c,etc all have 65535 nodes (incl. themselves)
There are two such subtrees under each level 3 node
65535 * 2 = 131070 plus the node itself = 131071

node | list length
8     3            =      3
9     3 + 131071   = 131074
10     4 + 131071*2 = 262146
11     4 + 131071*3 = 393217
12     6 + 131071*4 = 524290
13     6 + 131071*5 = 655361
14     7 + 131071*6 = 786433
15     8 + 131071*7 = 917505
=======
3670029 operations just to add the 3rd level nodes
+ (1048575-8) ops for the other nodes
========
4718596```
This is impressive. So it's correct to ignore the work of AddToTail? Maybe not.. then, how much is the complexity of FUNCTION2?

9. Originally Posted by Jacopo
then, how much is the complexity of FUNCTION2?
Well, the value 3670029 above is (using ** to mean exponentiation)
41 + 28 * (2**(H - 3) - 1) = 13 + 2**(H + 1.81) (where H is 20)
2**(H + 1.81) + 2**H (although I guess the 2**H is almost insignificant)

10. Originally Posted by john.c
Well, the value 3670029 above is (using ** to mean exponentiation)
41 + 28 * (2**(H - 3) - 1) = 13 + 2**(H + 1.81) (where H is 20)