J's answer to Delibas Muzo's Turkey question.
done
{{ upvoteCount }} Upvotes
clear
{{ downvoteCount * -1 }} Downvotes
Backward substitution method :
Assume first that n = 2^k
So , k = log2 (n)
Tn = n T(n/2)
= n (n/2) T(n/4)
= n (n/2) (n/4) T(n/8)
...
= n (n/2¹) (n/2²) (n/2³) .... (n/2^(k-1)) T(n/2^k)
= n^k / 2^(1 + 2 + 3 + ... + (k-1)) · T(1)
(because n = 2^k so n/2^k = 1)
= n^(k) / 2^(k(k-1)/2) · 1
(T(1) = 1, sum of terms from 1 to (k - 1) is done using ∑ n from 1st term to (n-1)th term)
= n^(k) / n^((k-1)/2)
= n^(k - k/2 + ½)
= n^(k/2 + ½)
= n^(½log2(n) + ½)
= √n^(log2(n) + 1)
Assume first that n = 2^k
So , k = log2 (n)
Tn = n T(n/2)
= n (n/2) T(n/4)
= n (n/2) (n/4) T(n/8)
...
= n (n/2¹) (n/2²) (n/2³) .... (n/2^(k-1)) T(n/2^k)
= n^k / 2^(1 + 2 + 3 + ... + (k-1)) · T(1)
(because n = 2^k so n/2^k = 1)
= n^(k) / 2^(k(k-1)/2) · 1
(T(1) = 1, sum of terms from 1 to (k - 1) is done using ∑ n from 1st term to (n-1)th term)
= n^(k) / n^((k-1)/2)
= n^(k - k/2 + ½)
= n^(k/2 + ½)
= n^(½log2(n) + ½)
= √n^(log2(n) + 1)
Date Posted:
4 years ago
360 Tutoring Program