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)
Then T belongs to big-theta (lg n)
No comments:
Post a Comment