Description

Assignment 3 – Proofs & Running Time Analysis

BST-MEDIAN ALGORITHM
Suppose that a binary search tree has nodes, all distinct, and of depth , where odd number. Design an efficient algorithm which runs in time that finds the medianvalued node of (note that since the number of nodes of the tree is odd, there is exactly one median-valued node).

PROOF OF CORRECTNESS

An algorithm, for a given computational problem, is correct if the following property holds:
If the algorithm is executed and the problem’s precondition is satisfied, then the execution of the algorithm eventually ends, and the problem’s postcondition is satisfied
No changes to the system state, that are not documented in the precondition and postcondition, should be caused by the execution of this algorithm if the precondition holds when the execution begins

This can be proven using the strong form of mathematical induction on , where there base cases and will be considered.

Basis step
Suppose, first, that . Tracing the algorithm: this causes the body of the third else-if statement to execute, with the value of the only node returned as output — as required for this case as it would be the median.
Now suppose that . Since the number of nodes has to be odd, this implies that the size of both the left and right subtree are . Tracing the algorithm: this will also cause the
body of the third else-if statement to execute, returning the current root node as the median, which is still the root node of the entire tree.

Inductive step
Let be an integer such that . It is necessary and sufficient to use the following inductive hypothesis to prove the following inductive claim:

Inductive hypothesis: Suppose that is a nonnegative integer such that . If the algorithm findBSTMedian() is executed given a binary search tree with depth as input then this execution of the algorithm eventually terminates, with the median of the binary search tree with depth being returned.
Inductive claim: If the algorithm findBSTMedian() is executed given a binary search tree with depth as input then this execution of the algorithm eventually terminates, with the median of the binary search tree with depth is returned.

Proof
Suppose this algorithm is executed on a binary search tree with depth .

Lines 5-7 check if the root node is null. If it is not null, then:
Line 8 computes the size of the node immediately to the right of the current root ‘s node. The depth of this subtree is now , or .
It now follows by the inductive hypothesis that an execution of this algorithm with a binary search tree of depth eventually terminates, with the median of this tree being returned.
One can see by inspection of the code that this does not change this binary search tree or have other undesired side-effects, so the algorithm findBSTMedian() can be considered correct.

RUNNING TIME ANALYSIS

We can analyze the runtime of this algorithm using the uniform cost criterion in order to form a function .
Suppose this algorithm is executed on a binary search tree with nodes, all distinct, and of depth , where is an odd number.
Then:
Line 5 costs 1 step, as it is a simple check to see if the root node is null
In the case that it is, line 6 costs 1 step as well
Line 8 costs 1 step to set the rightSize variable using the provided size property
Lines 9, 12 and 15 each cost 1 step, as they are if statements comparing the two sizes
Line 10 contains a recursive call to the function which costs * steps at worst
Line 13 contains a recursive call to the function which costs steps at worst
Lines 16 and 19 each cost 1 step, as they are simply returning the median node

* I was able to arrive at this upper bound by tracing the algorithm for various types of binary search trees in depths and and identying a pattern for the number of steps each recursive call took at most.

PROOF OF LINEAR RUNTIME
We will now prove that the runtime of the findBSTMedian() algorithm is in , by application of the definition.
By definition of , we are required to show that there exists a constant and a constant such that for all .

Let and .
Let be an arbitrarily chosen element in the range of such that . We must prove that the claim holds for this choice of .

. Since was arbitrarily chosen from , it follows that
such that . Since and are
constants, this establishes the claim that they are existentially quantified, as needed to
We have now proved a result for all in the range of such that .

Another way of proving that this algorithm is in linear time is using a limit test for .
By definition of the theorem, if exists and is a real constant — so that in particular, it is not
equal to — then

Since 4 is a real and non-negative constant, it now follows by the Limit Test for that this algorithm is in , where is the depth of the binary search tree.