Assignment 2

So, Assignment 2! Finally I get to finish off Ternary Trees. I've got a working formula; hope the proof makes sense.

Question 2 should lead me to something with log(base 7) in it. Of course I can change it to lg since if log7(a) = x then x.lg(7) = lg(a) by simple algebra:

log7(a) = x ==> 7^x = a (what log7) means!
lg(7^x) = lg(a), taking lg (log base 2) of both sides
x.lg(7) = lg(a), by 3rd law of logarithms

so that's not so bad. Still, I guess we need to prove it for non-powers-of-7. Since we did something like it in class for mergesort, that's probably a good example to follow.

Question 3: looks like G(n) = 1, if n <3; G(n) = if n >= 3 will do it (I guess I shouldn't post my formula in public, especially if it's wrong!)

Question 4: Two things occur to me: 1. The method used to divide the problem is not that relevant to the proof, so long as it produces an index between b and e, inclusive. 2. I cannot conceive that this question would be here if there were a counterexample. Sounds too much like a trick to me and wouldn't help me learn proof techniques.

So, I guess I'll prove it, if I can. Probably the approach in the course notes for proving recursive binary search will work. Hope I can use that without it looking too much like copy and paste.