Web hosting provider - 286 ARITHMETIC 4.3.3 Thus there is a constant
286 ARITHMETIC 4.3.3 Thus there is a constant c such that tk i c&k&k + (2rk + l)tk-1. To complete the estimation of tk we can prove by brute force that for some constant C. Let us choose C > 2Oc, and let us also take C large enough so that (18) is valid for k < kc, where kc will be specified below. Then when k > ko, let &k = lgqk, & = lgrk; we have by induction tk 5 CqkT; lgrk + (2?-k + 1)cqk22 5G = cqk+122.5d==(771 + r12), where ql = :Rk2Rk-2.5fi < $jRk2-R* < 0.05, c r/s = a+; 22.5(G-&zTd + 2-l/4 < 085 , . ( > since as k + co. It follows that we can find ko such that ~2 < 0.95 for all k > k,,, and this completes the proof of (18) by induction. Finally, therefore, we may compute r(n). Since n > q-1 + qk-2, we have qk-1 < n; hence Tkpl = 2lGJ < 26, and qk =rk-lqk-1 < n2 &G , Thus and, since T(n) = o(qk) + t&-l, we have finally derived the following theorem: Theorem C. There is a constant cc such that the execution time of Algorithm C is less than con23.5fi cycles. 1 Since n23.56 = n1+3.5/& th is result is noticeably stronger than Theorem A. By adding a few complicaiions to the algorithm, pushing the ideas to their apparent limits (see exercise 5), we can improve the estimated execution time to T(n) = O(n2fi logn). (19)