Recurrence solving in Algorithm

Question

I was doing the exercise and I got stuck -.-. This is the task I have to do.

The solution: I dont get the step of the yellow one. I tried to understand but I lack of the knowledge of the logarithm. Can you explaine

Thanks for your explanation!

Whatever the log basis is, you have log(a*b) = log(a) + log(b) and consequently log(1/a) = -log(a) — Damien
– Damien, Commented Jan 7, 2020 at 11:18
Thanks Damien for you explanation. But I still don't get it. 2(n/2)log2 = log2(n) log2(n/2) log2(n/2) = -log2(n/2) Because n/2 = its still will stay as it is. — Sayuri
– Sayuri, Commented Jan 7, 2020 at 11:41
log(n/2) = log(n) - log(2) . I don't understand what is unclear — Damien
– Damien, Commented Jan 7, 2020 at 11:45
@Sayuri Damien gave you everything to understand how to obtain the yellow line... — Jean-Baptiste Yunès
– Jean-Baptiste Yunès, Commented Jan 7, 2020 at 11:45
@Sayuri log2 is a function this log2(n/2) is the value of it at n/2. It is not log2 x n/2! Then from Damien's log2(n/2) is log2(n)-log2(2) and as 2(n/2)=n... — Jean-Baptiste Yunès
– Jean-Baptiste Yunès, Commented Jan 7, 2020 at 11:48

A.A. · Accepted Answer · 2020-01-07 12:10:46Z

1

keep in mind that log ab = log a + log b also log (1/a) = - log a

So when you have 2(n/2) log(n/2) you can write log(n/2) as log(1/2 x n) which using log ab = log a + log b equals log(n) + log(1/2)

2(n/2) log(n/2) = 2(n/2) (log n + log(1/2)) = n(log n + log(1/2))

Also log (1/a) = - log a, and hence log(1/2) = - log 2

That is how you get

2(n/2) log(n/2) + n = 2(n/2) (log n + log(1/2)) + n = n(log n + log(1/2))

= n(log n - log 2 ) + n

Since log 2 = 1 in base 2 you will have n(log n - log 2 ) + n = n(log n - 1) + n = n lg n

answered Jan 7, 2020 at 12:10

A.A.

1,04716 silver badges29 bronze badges

Sign up to request clarification or add additional context in comments.

1 Answer 1