Understanding Logarithms: Solving Recurrence Relations Explained | O(n log n)

[theintarnets]

I'm having trouble understanding the last two lines of a recurrence relation:

2^{(log₂ n)} + kn
= n + log₂ 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)

 

[Simon Bridge]

Where did k go? Where did + n come from? and what happened to the 2?

From the rest of the relation:

Suppose (n/(2^k)) = 1:
Then, n = 2^k => k = log n

 

[sherrellbc]

What value do I raise the constant "2" to, in order to resolve the function 2^n?

That is what 2^(log2 n) is saying.

 

[Simon Bridge]

@theintarnets: sherrellbc has provided a good hint:

That is what 2^(log₂ n) is saying.

i.e. what is the definition of the logarithm?

$a^b=c$ then $\log_a(c)=b$ so if you do $a^{\log_a(c)}$ .. what do you get?
(Try it out using base 10.)

 

[sherrellbc]

You tell me: what is the definition of a logarithm?

I take it you understand "where the k went" now?

$a^b=c$ then $\log_a(c)=b$ so if you do $a^{\log_a(c)}$ .. what do you get?
(Try it out using base 10.)

I was making a comment. I think you mistook me for the OP.

 

[Simon Bridge]

I was making a comment. I think you mistook me for the OP.

Yes I did - my apologies :D
Edited.