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?

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.

Quote:

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? :(

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.

Quote:

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?

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

Quote:

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

Quote:

Originally Posted by Salem

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

you are right, but my reasoning remains:D

Quote:

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?

Quote:

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)

Quote:

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

I'm not that great at math. But it seems to simplify to 4.5n, which would make it linear.