patternMinorCanonical
Time complexity of tree algorithm
Viewed 0 times
algorithmtreecomplexitytime
Problem
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)$?
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)$?
Solution
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)$.
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)$.
Context
StackExchange Computer Science Q#165081, answer score: 3
Revisions (0)
No revisions yet.