Time Complexity of Recursive Algorithm

[nathanhaigh]

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

[Rashakil Fol]

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.

[amber 126]

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;
               }
         }
}

[jl.lakhnai]

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

[Mavericks]

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

http://www.cs.ucf.edu/~dmarino/ucf/cop3502/lec_biswas/recursion12.pdf
This will help understand time complexity of recursive function. Explanation is quite clear