How does this algorithm have complexity of O(n^2)?

Question

Let v be a node of a tree T. The depth of a node v can defined as follows:

• If v is the root, then the depth of v is 1.
• Otherwise, the depth of v is 1 plus the depth of the parent of v.

Based on the above definition, the recursive algorithm depth, shown in the below Algorithm, computes the depth of a node v of Tree by calling itself recursively on the parent of v, and adding 1 to the value returned.

Algorithm depth(T, y):

• Step 1: If T.isRoot(v), then return 1
• Step 2: Else, return 1 + depth(T, T. parent(v))

The height of a tree T is equal to the maximum depth of an external node of T. While this definition is correct, it does not lead to an efficient algorithm. Indeed, if we were to apply the above depth-finding algorithm to each node in the tree T, we would derive an O(n²)-time algorithm to compute the height of T.

According to above statement how can it be O(n²)? If we try this algorithm on every external node, then it takes O(n), and to find maximum it will O(n). So the total complexity should be O(n)+O(n) = O(2n)==O(n), right?

Answer 1

In asymptotic notation, n^2 could mean, for each node you are visiting variable number of nodes which is at max n or n - 1. Let's consider this:

When you call the recursive function for the node 1, it immediately returns, but when you call it for node 5, you need to recomputes depth for all node till node 1, which means you visited all other nodes as you're not using memoization. Hence, for each node you are visiting [1 to n-1] nodes.

Answer 2

The worst case for the algorithm is a tree that is not balanced. For example, a tree as shown below:

The tree above has 5 external nodes and 5 internal nodes, so exactly half the nodes are external nodes. Starting from A, there is one parent. Starting from B, there are 2, etc. So the total number of parents (P) that are visited is 1+2+3+...+(n/2).

Using the formula for the sum of natural numbers we have P = (n/2)(n/2 + 1)/2 = (n^2 + 2n)/8. Ignoring the constant factor (8), and the less dominant term (2n), we see that P is O(n^2).

Answer 3

If we try this algorithm on every external node than it take O(n)

This is not correct. You will apply the algorithm n times, where each call takes O(n) time, which leads to O(n^2) time in total.

This is of course assuming there is no caching/memoization of results (so we are doing a lot of repeated work). If there were, then it would indeed be O(n) in total.