# Thread: Asymptotic complexity help

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)
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? 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.
Ok, thanks for your answer. Somebody else?  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)
tossing out the 13 as insignificant, and adding in about 2**20 ops for adding to the head, gives
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)
tossing out the 13 as insignificant, and adding in about 2**20 ops for adding to the head, gives
2**(H + 1.81) + 2**H (although I guess the 2**H is almost insignificant)
Pls, in terms of asymptotic function This is really hard to understand for me!
I guessed was (n^2) when the tree depth is same or more than 3, and (n) when the depth is less then 3 11. I'm not that great at math. But it seems to simplify to 4.5n, which would make it linear. Popular pages Recent additions #### Tags for this Thread

addtohead, complexity, depth, list, number 