Saturday, 3 November 2012

bad term test

It was really bad unlike the first one because we have not much time to do it. Only fifty minutes for an unwinding, and 2 long proofs. Most of my friends had the same feeling, so I hope we would receive bell-curve.

An interesting question on the term test was to prove that 
c0 lg n <= T(n) <= c1 lg n which implies T belongs to big-theta (lg n).
To prove this question, I used the following structure

case1: c0 lg n <= T(n) 
           ...
           Then case 1 holds

case2: T(n)  < = c1 lg n
           ...
          Then case 2 holds

Then since both cases hold, we conclude that c0 log n <= T(n) <= c1 log n.
Then T belongs to big-theta (lg n)

No comments:

Post a Comment