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)) 
    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]])

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!

8 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.

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)

Edited by mike_2000_17: Fixed formatting

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

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.