4.3-2
Show that the solution of $T(n) = T(\lceil n/2\rceil)+ 1 $ is $O(lg n)$.
let $T(n) = c lgn $
$$T(n) = c lg [n/2]+1 $$
$$T(n) = c lg n - c lg2 +1 $$
$$T(n) = c lg n - ( c lg2 -1) $$
$$c lg2 -1 \geq 0 $$
$$c \geq 1 $$
$$T(2) = \theta(2) <= c $$
for big value of c except when n = 1 the above equation is true.
No comments:
Post a Comment