# Time complexity of tree algorithm

I'm new to recurrence relations and master theorem so trying to learn. Say there's an algorithm $$A$$ whose input is the root of a binary tree $$T$$. $$A$$ recurses so that it's called on each and every node in $$T$$ exactly once. The time complexity of $$A$$ called on a node $$X$$ is $$O(number\:of\:nodes\:in\:subtree\: rooted\:at\:X)$$.

What's the overall big O time complexity of $$A$$ (probably in terms of $$N$$, the total number of nodes in $$T$$)?

My (informal) approach is to imagine $$T$$ as a maximally imbalanced tree (single line of nodes straight down). Then the time complexities of the nodes starting from root is $$N$$, $$N-1$$, .... $$1$$, of which there are $$N$$. That becomes $$(N+1)*(N/2) == N^2/2+N/2 == O(N^2)$$.

However I'm not sure this holds for other types of binary trees (such as perfect). I'm struggling to come up with a formal approach.

I'm trying to use master theorem and believe the recurrence relation is $$T(n) = 2T(n/2) + f(n)$$.

$$c_{crit} = log_2 2 = 1$$.

Worst case of $$f(n)$$ is at root of $$T$$ which is $$O(n)$$, so $$f(n) = O(n^c)$$ gives $$c = 1$$, and thus it cannot be Case 1 or 3 because $$c == c_{crit}$$. So it must be Case 2. But how do I determine the value of $$k$$ in $$f(n) = \theta(n^{c_{crit}}log^{k}n)$$?

Note that the complexity of the algorithm depends on the tree $$T$$. For the maximally imbalanced tree, as you computed the complexity is $$O(n^2)$$. Another important observation is that the complexity on this particular type of tree is $$\Omega(n^2)$$.
If you take a perfectly balanced complete tree, then then the root node has cost $$n$$; nodes at level $$1$$ have costs at most $$n/2$$; and so on... If you sum up the costs, you get $$n + 2 \cdot n/2 + 4 \cdot n/4 + \dots + n \cdot 1 = O(n \log n)$$. Moreover, the complexity over this particular type of tree is $$\Omega(n \log n)$$.
Now, let us talk about any general tree. Any node of the tree has cost at most $$n$$. Suppose we assume this worst cost for every node in the tree, then the complexity is at most $$n^2 = O(n^2)$$. Simple! This complexity is tight for general tree, since you already showed a worst case example of a maximally unbalanced tree to be $$\Omega(n^2)$$.
• Thanks! Questions: 1. "complexity on this particular type of tree is $\Omega(n^2)$" -> Why Omega? Does this mean $O(n^2)$ is incorrect here (but you still wrote that the complexity is $O(n^2)$ before and at the end of your answer)? 2. Your process makes sense to me (except for the above question). However I associate formal proofs with the master theorem. Is using the theorem doable with this algorithm, and if so how? Commented Jan 17 at 17:43
• @onepiece Both $O(n^2)$ and $\Omega(n^2)$ are correct for the maximally unbalanced trees. Note that you computed the complexity as $(N+1)N/2$, which is both $O(n^2)$ and $\Omega(n^2)$. The above proof is also formal. I personally never use master theorem. Firstly, it has many cases. Secondly, I have never required it; a simple tree/substitution based schemes have always worked for me. Commented Jan 17 at 17:53
• "Both $𝑂(𝑛^2)$ and $\Omega(𝑛^2)$ are correct for the maximally unbalanced trees" -> is this because complexity for those trees is always $n^2$? Then is $\Theta(n^2)$ also correct? Similarly, all three big notations of $nlogn$ are correct for perfectly balanced complete trees. Is this why we usually care about the big O (because if a given algorithm could have complexity 1, $n$, or $n^2$ depending on input, saying it's $\Omega(1)$ is correct but much less meaningful than $O(n^2)$? Commented Jan 17 at 18:49
• @onepiece Yes. Yes, $\Theta(n)$ is also correct. Yes all three notations are correct for balanced trees as well. Yes, we usually care about big O notation; however saying that complexity is $O(n^3)$ or $O(n^4)$ is also correct for you problem. But is not tight. Therefore, $\Omega()$ gives a lower bound as well. In short, $O$ + $\Omega$ together are more meaningful; Commented Jan 17 at 18:53