Thread: Asymptotic complexity help

  1. #1
    Registered User
    Join Date
    Feb 2018
    Posts
    21

    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?
    Last edited by Jacopo; 03-30-2018 at 07:51 AM.

  2. #2
    Registered User
    Join Date
    May 2009
    Posts
    3,625
    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.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  3. #3
    Registered User
    Join Date
    Feb 2018
    Posts
    21
    Quote Originally Posted by stahta01 View Post
    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. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,312
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Registered User
    Join Date
    Feb 2018
    Posts
    21
    Quote Originally Posted by Salem View Post
    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. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,312
    I think you've got head and tail mixed up.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  7. #7
    Registered User john.c's Avatar
    Join Date
    Dec 2017
    Posts
    615
    Quote Originally Posted by Salem View Post
    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
    Last edited by john.c; 04-01-2018 at 10:37 AM.
    The world hangs on a thin thread, and that is the psyche of man. - Carl Jung

  8. #8
    Registered User
    Join Date
    Feb 2018
    Posts
    21
    Quote Originally Posted by Salem View Post
    I think you've got head and tail mixed up.
    you are right, but my reasoning remains

    Quote Originally Posted by john.c View Post
    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?
    Last edited by Jacopo; 04-01-2018 at 12:13 PM.

  9. #9
    Registered User john.c's Avatar
    Join Date
    Dec 2017
    Posts
    615
    Quote Originally Posted by Jacopo View Post
    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)
    The world hangs on a thin thread, and that is the psyche of man. - Carl Jung

  10. #10
    Registered User
    Join Date
    Feb 2018
    Posts
    21
    Quote Originally Posted by john.c View Post
    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
    Last edited by Jacopo; 04-01-2018 at 02:47 PM.

  11. #11
    Registered User john.c's Avatar
    Join Date
    Dec 2017
    Posts
    615
    I'm not that great at math. But it seems to simplify to 4.5n, which would make it linear.
    The world hangs on a thin thread, and that is the psyche of man. - Carl Jung

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 1
    Last Post: 02-05-2014, 11:03 PM
  2. asymptotic notation clarify
    By monkey_c_monkey in forum Tech Board
    Replies: 6
    Last Post: 10-05-2012, 06:12 PM
  3. Asymptotic estimate
    By jturner38 in forum C++ Programming
    Replies: 4
    Last Post: 12-14-2010, 07:39 PM
  4. Sorting (asymptotic) complexity problem
    By Petike in forum C++ Programming
    Replies: 8
    Last Post: 01-20-2009, 07:15 AM
  5. Algorithmic Complexity + Asymptotic Notations
    By koodoo in forum C Programming
    Replies: 5
    Last Post: 09-03-2006, 02:25 AM

Tags for this Thread