I am trying to solve series of the form,
T(n) = T(n/4) + clog(n)
I am able to formulate a general formula for the T(n) term for the nth term. Its of the form
(2^k)T(n/2^2k) + k
k = 8clog(n/64) + 4clog(n/16) + 2clog(n/4) + clog(n)
but am having a hard time, summarizing the k terms together into a single formula. I have a basic idea of geometric and arithmatic progression, but cant figure this one out. Any hints would be greatly appreciated.
Examining how you expanded your terms, did you mean the following recurrence?
$$T(n) = 2\:T\left( \frac{n}{4} \right) + c \log(n)$$
If so, solving it by rolling out the sequence and gleaning from the pattern is difficult. If you only want to know what $\Theta(T(n))$ is, then refer to the Master Theorem for solving recurrences of the form $$T(n) = a\:T\left( \frac{n}{b} \right) + f(n)$$
For this particular example, the Master Theorem classifies that $T(n) \in \Theta\left( n^{\log_4(2)} \right) = \Theta\left(\sqrt{n}\right)$. But why?
Without using the Master Theorem, these recurrences can be solved using a (clever) inductive argument. To do so, first prove that there exist (not necessarily positive) constants $d$ and $e$ such that $T(n) \le d\sqrt{n} + e \log(n)$.
Likewise, you can use a symmetric induction argument for the lower bound.
As always, don't forget about the base case!