- #1

theintarnets

- 64

- 0

2

^{(log2 n)}+ kn

= n + log

_{2 }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)