- #1
theintarnets
- 64
- 0
I'm having trouble understanding the last two lines of a recurrence relation:
2(log2 n) + kn
= n + log2 n * n
I get the rest of the recurrence relation, but I don't understand how those two became equivalent. Where did k go? Where did + n come from? and what happened to the 2?
Here is the rest of the relation in case it is needed to understand those two lines:
T(1) = 1
T(n) = T(n/2) + T(n/2) + n
= 2 T(n/2) + n
= 2 [2 T(n/4) + (n/2)] + n
= 4 T(n/4) + 2n
= 4 [2 T(n/8) + (n/4)] + 2n
= 8 T(n/8) + 3n
= ...
= 2^k T(n/(2^k)) + k n
Suppose (n/(2^k)) = 1:
Then, n = 2^k => k = log n
= 2^(log_2 n) * T(1) + k n
= 2^(log_2 n) * 1 + k n
= 2^(log_2 n) + k n
= n + (log_2 n) * n
=> O(n log n)
2(log2 n) + kn
= n + log2 n * n
I get the rest of the recurrence relation, but I don't understand how those two became equivalent. Where did k go? Where did + n come from? and what happened to the 2?
Here is the rest of the relation in case it is needed to understand those two lines:
T(1) = 1
T(n) = T(n/2) + T(n/2) + n
= 2 T(n/2) + n
= 2 [2 T(n/4) + (n/2)] + n
= 4 T(n/4) + 2n
= 4 [2 T(n/8) + (n/4)] + 2n
= 8 T(n/8) + 3n
= ...
= 2^k T(n/(2^k)) + k n
Suppose (n/(2^k)) = 1:
Then, n = 2^k => k = log n
= 2^(log_2 n) * T(1) + k n
= 2^(log_2 n) * 1 + k n
= 2^(log_2 n) + k n
= n + (log_2 n) * n
=> O(n log n)