# Help With Logarithms

1. Jul 1, 2013

### theintarnets

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. Jul 2, 2013

### Simon Bridge

From the rest of the relation:

3. Jul 2, 2013

### 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.

4. Jul 2, 2013

### Simon Bridge

@theintarnets: sherrellbc has provided a good hint:
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.)

Last edited: Jul 2, 2013
5. Jul 2, 2013

### sherrellbc

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

6. Jul 2, 2013

### Simon Bridge

Yes I did - my apologies :D
Edited.