Question

Solve the following recurrence relation (without using Master Theorem)
C(n) = C(n/2) + logn, for n > 1. C(1) = 0

Answer 1

Answer on Question #73687 - Algorithms

$$C _ {2} = C _ {1} + \log 2 = \log 2,$$ $$C _ {4} = \log 2 + \log 4,$$ $$C _ {8} = \log 2 + \log 4 + \log 8,$$ $$\cdots$$ $$\begin{array}{l} \Rightarrow C _ {n} = \log 2 (1 + 2 + \dots + \log_ {2} n), \\ C _ {n} = \log 2 (1 + \log_ {2} n) \frac {\log_ {2} n}{2}. \end{array}$$

Answer provided by AssignmentExpert.com