Thread: 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.

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.

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

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

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?

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)

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.