Given a binary tree, is it a search tree?
In part A students are asked to write the function ValsLess:
In Part B, students are asked to write IsBST using ValsLess and assuming that a similar function ValsGreater exists. The solution is shown below:
Before continuing you should try to determine/guess/reason about what the complexity of IsBST is for an n-node tree. Assume that ValsLess and ValsGreater both run in O(n) time for an n-node tree.
What is the asymptotic complexity of the function DoStuff shown below. Why? Assume that the function Combine runs in O(n) time when |left-right| = n, i.e., when Combine is used to combine n elements in the vector a.
You may recognize this function as an implementation of Mergesort. You may also remember that the complexity of Mergesort is O(n log n) fo an n-element array/vector. How does this relate to the function IsBST?
We'll make a mathematical definition:
Then we have the following relationship:
T(n) = 2 T(n/2) + O(n) [the O(n) is for Combine] T(1) = O(1)
This relationship is called a recurrence relation because the function T(..) occurs on both sides of the = sign. This recurrence relation completely describes the function DoStuff, so if we could solve the recurrence relation we would know the complexity of DoStuff since T(n) is the time for DoStuff to execute.
How does this relate to the time for IsBST to execute? If you look carefully at the code for IsBST you'll see that it has the same form as the function DoStuff, so that IsBST will have the same recurrence relation as DoStuff. This means that if you accept that DoStuff is an O(n log n) function, then IsBST is also an O(n log n) function.
We'll write n instead of O(n) in the first line below because it makes the algebra much simpler.
T(n) = 2 T(n/2) + n = 2 [2 T(n/4) + n/2] + n = 4 T(n/4) + 2n = 4 [2 T(n/8) + n/4] + 2n = 8 T(n/8) + 3n = (ask your class to fill in this line, or you fill it in) you should have written: 16 T(n/16) + 4n = 2^{k} T(n/2^{k}) + k n [this is the Eureka! line]
You could ask students to fill in parts of the last line. Note that the last line is derived by seeing a pattern --- this is the Eureka/leap of faith/practice with generalizing mathematical patterns part of the problem.
We know that T(1) = 1 and this is a way to end the derivation above. In particular we want T(1) to appear on the right hand side of the = sign. This means we want:
n/2^{k} = 1 OR n = 2^{k} OR log_{2} n = k
Continuing with the previous derivation we get the following since k = log_{2} n:
= 2^{k} T(n/2^{k}) + k n = 2^{log2 n} T(1) + (log_{2}n) n = n + n log_{2} n [remember that T(1) = 1] = O(n log n)
So we've solved the recurrence relation and its solution is what we "knew" it would be. To make this a formal proof you would need to use induction to show that O(n log n) is the solution to the given recurrence relation, but the "plug and chug" method shown above shows how to derive the solution --- the subsequent verification that this is the solution is something that can be left to a more advanced algorithms class.
Before continuing, or with your class, try to fit each of the above recurrence relations to an algorithm and thus to its big-Oh solution. We'll show what these are below. Of course for practice you can ask your students to derive the solutions to the recurrence relations using the plug-and-chug method.
Recurrence | Algorithm | Big-Oh Solution |
---|---|---|
T(n) = T(n/2) + O(1) | Binary Search | O(log n) |
T(n) = T(n-1) + O(1) | Sequential Search | O(n) |
T(n) = 2 T(n/2) + O(1) | tree traversal | O(n) |
T(n) = T(n-1) + O(n) | Selection Sort (other n^{2} sorts) | O(n^{2}) |
T(n) = 2 T(n/2) + O(n) | Mergesort (average case Quicksort) | O(n log n) |
The solution below correctly solves the problem. It makes a call to the partition function from Quicksort. Assume that the partition function runs in O(n) time for an n-element vector/vector-segment. For completeness we'll include a partition function at the end of this document.
For an n-element vector a the call FindKth(a,0,n-1,k) returns the k^{th} element in a:
What is the big-Oh complexity of FindKth in the worst-case and in the average-case. Since it's difficult to reason precisely about average-case without more mathematical sophistication than we want to use, assume that things behave nicely in the average-case. As it turns out, this gives the right answer for most definitions of average-case. In later courses we can define more precisely what average case means.
If T(n) is the time for FindKth to execute for an n-element vector, the recurrence relation in the worst-case is:
Where the O(n) term comes from Partition. Note that there is only one recursive call made in FindKth.
This is one of the big-five recurrences, it's solution is O(n^{2}) so that FindKth in the worst-case is an n^{2} function.
The recurrence relation for the average case is
This isn't one of the "big five", so you'll have to solve it yourself to determine the average-case complexity of FindKth. Hint: it's pretty good.