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
9 Years
Discussion Span
Last Post by Mavericks

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.

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