3
$\begingroup$

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)$?

$\endgroup$

1 Answer 1

3
$\begingroup$

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)$.

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – onepiece
    Commented Jan 17 at 17:43
  • 1
    $\begingroup$ @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. $\endgroup$ Commented Jan 17 at 17:53
  • $\begingroup$ "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)$? $\endgroup$
    – onepiece
    Commented Jan 17 at 18:49
  • 1
    $\begingroup$ @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; $\endgroup$ Commented Jan 17 at 18:53
  • $\begingroup$ Thank you, very clear and helpful! $\endgroup$
    – onepiece
    Commented Jan 17 at 22:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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