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