Assignment 3

Runtime Analysis for Height Function

public int height() {
   return height(this.root);
}
 
private int height(Node node) {
   return node != null ?
   	1 + Math.max(height(node.left), height(node.right)) :
   	-1;
}

---

Running Time

As there are no conditional logic statements in the public height function before recursion begins, every case for this function is the worst case.

The above algorithm consists of two parts:

Part	Purpose	Runtime Cost
A	Starting the algorithm	$T_A(N)$
B	Recursive Executor	$T_B(N)$
Since these parts are sequential, we can find the overall runtime cost $T_N$ as:
$T_N=T_A(N)+T_B(N)$

Public Height Function

public int height() {
	return height(this.root);
}

The public height function simply exists in order to start the recursive section off at the root element. Hence, $T_A(N)$ runs in $\Theta (1)$ runtime as all that is happening is a function call.

Private overloaded recursive height function

private int height(Node node) {
	return node != null ?
		1 + Math.max(height(node.left), height(node.right)) :
		-1;
}

The private height function is responsible for the actual calculation of the height.

This is accomplished recursively as follows:

• Base Case:
  • If a null node is encountered the height returned is the default value as per the assignment spec $-1$
• Height Calculation:
  • Otherwise the height is the maximum of the height of the node’s children nodes, $+1$ for the current height.

Hence, the height must receive a value from each element of the node tree, therefore the runtime for $T_B(N)$ must be $\Theta (N)$.

Conclusion

$T_N=T_A(N)+T_B(N)$ $T_N=\Theta (1)+\Theta (N)$ $T_N=\Theta (N)$

Hence, the worst case asymptotic runtime for the height function is $\Theta (N)$.