Assume we have a perfectly balanced Binary tree. We have the following algorithm: For each passed node, traverse through all its ancestors and then do the same algorithm for the left and right child of the node.

So, the way I try to find the Big-O complexity is this: There are O(N) nodes in the tree and each has O(log2N) ancestors, so overall we'll have O(N*log2N) complexity if we start the algorithm from the root.

Now consider another problem for the same Binary tree: For each node, go to its left and right child. If the node doesn't have any children, for each ancestor, go through all the previous ancestors.

Now my attempt for finding the complexity: We basically keep going through every node until we reach the leafs. There are N/2 leafs in a perfect Binary tree with N nodes and for each leaf we have (log2N) ancestors. Since for each ancestor we have to traverse every previous, the overal compexity when we're on a leaf is O(Log2(N)^2), so overall complexity becomes O(N*log2(N)^2).

The problem is that I think the algorithms basically do the same thing. Why do I get different complexities for them?

  • $\begingroup$ You are confused as to what N is. There are O(N) nodes in the tree, but each does not have $O(log_2N)$ ancestors. Each has $O(log_2h)$ ancestors, where h is the height of the current node. $\endgroup$ – Sagnik Aug 9 '15 at 5:55

They're not the same thing. Consider some node $x$. Ask yourself how many times the algorithm does the operation "iterate through all the ancestors of $x$".

The first algorithm does this operation once. The second algorithm does this operation $k$ times, where $k$ is the number of descendants of $x$. So, it's no surprise that the second algorithm takes longer: it's doing a lot more repeated work.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.