SupposewehaveT(n)≤c=O(1)foralln≤3,andforeveryn≥4,wehave ，T(n)<=T(n/4)+T(0.75*n) + c*n,Use Mathematical Induction to prove that T (n) = O(n log n) for all n ≥ 4.

证明：首先，假设T(n)<=c*n，当n=4时，我们有T(4)<=c*4，即T(4)<=O(1)；假设T(k)<=c*k*log k，当k>4时，由T(n)<=T(n/4) T(0.75*n)和T(n)<=c*n可得：T(n)<=(c/4)*n*log(n/4)+(3/4)*c*n<=c*n*(log n-log 4+3)<=c*n*log n，即T(n)<=c*n*log n，由归纳法可知T(n)<=c*n*log n 对于所有n >= 4。因此，T(n)=O(n log n) 对于所有n>=4。

相关问题

SupposewehaveT(n)≤c=O(1)foralln≤3,andforeveryn≥4,wehave ，T(n)<=T(n/4)+T(0.75n*)+cn,Use Mathematical Induction to prove that T (n) = O(n log n) for all n ≥ 4.

用数学归纳法证明T(n)=O(nlogn)，可将n分为三种情况。首先，当n=4时，T(n)≤T(1)=c=O(1)，由假设可知T(n)<=T(n/4) T(0.75n*) cn，故T(4)≤T(1) T(3) T(3) c4，即T(4)≤c4，即T(4)=O(4)，证明了当n=4时T(n)=O(n)。其次，假设当n=k时T(k)=O(k)成立，即T(k)≤ck，则当n=k+1时T(k+1)≤T(k/4)T(3k/4)T(3k/4)ck+1，即T(k+1)≤ck+1，即T(k+1)=O(k+1)，证明了当n=k+1时T(n)=O(n)。最后，由数学归纳法可知，当n≥4时，T(n)=O(nlogn)。

SupposewehaveT(n)≤c=O(1)foralln≤3,andforeveryn≥4,wehave ，T(n)<=T(n/4)+T(0.75*n)+cn,Use Mathematical Induction to prove that T (n) = O(n log n) for all n ≥ 4.

用数学归纳法证明T(n) = O(n log n) 对于所有n ≥ 4，首先，假设T(n) ≤ cn，其中c是一个正常数，对于n ≥ 4。令m = n/4，则T(m) ≤ c m，因为T(n) ≤ T(m)，故T(n) ≤ c m，即T(n) ≤ c n/4。同样，令m = n/2，有T(m) ≤ c m，因此T(n) ≤ c n/4 ≤ c n/2。再令m = 0.75n，有T(m) ≤ c m，故T(n) ≤ c n/2 ≤ c 0.75n，因此T(n) ≤ c n，即T(n) = O(n)。现在，使用数学归纳法，可以得出结论T(n) = O(n log n)，对于所有n ≥ 4。