0

I'm new to this stuff, so bare with me!
I'm trying to determine the time complexity of a recursive algorithm which reverses the branches of a tree. The algorithm in R goes as follows:

rev <- function (x) {
    if (is.leaf(x)) 
        return(x)
    k <- length(x)
    if (k < 1) 
        stop("dendrogram non-leaf node with non-positive #{branches}")
    r <- x
    for (j in 1L:k) r[[j]] <- rev(x[[k + 1 - j]])
    midcache.dendrogram(r)
}

where:
x = a node in a tree e.g. root, leaf or internal
k = the number of children for a given node
r[[i]] OR x[[i]] = is child i of a node

I understand that the complexity will vary depending on the structure of the tree. For instance a completely binary tree will have 2n-1 nodes (including the root, leaves and all internal nodes) - which I think is the worst case as the number of times that the rev() function is called recursively is 2n-2 (all nodes excluding the root). I think the best case is for a tree with a polytomy at the root, such that there are only n+1 nodes i.e. the root plus n leaves coming from the root.

I've never tried to calculate time complexity before, but from reading previous posts I think I could for non-recursive algorithms, but I don't know where to start for this algorithm!

Any help or hints appreciated!
Nathan

5
Contributors
4
Replies
10
Views
8 Years
Discussion Span
Last Post by Mavericks
0

Well in your case, the number of times you call rev is equal to the number of leaves and non-leaf nodes in your tree. And each call to rev results in a constant amount of work, independent of child calls.

So the running time here is going to be proportional to the number of 'nodes' and leaves in your tree.

-1
y=0;
x=0;
for (i=n; i>0;i=i-1)
{ y=y+1;}

for (i=1;i<=n;i=i*3)
{      for (j=1;j<=3n;++j)
       {
         for(k=0;k<n; k=k+5)
              {
                 x=x+5;
               }
         }
}

Edited by mike_2000_17: Fixed formatting

Votes + Comments
I do not see connection to OP's question, old thread
-1

how to find the time complexity of any algorithm
and also describe with examples
please help

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.