Solving Recurrence Equations

I am trying to solve this Recurrence Equation and convert it into big O notation using substitution T(n) = T(n/2) + c
So...
I calculated:

Code:

---

T(n) = T(n/4) + 2c
T(n) = T(n/8) + 3c
T(n) = T(n/2^k) + kc

---

Now I'm lost. Some resources talk of setting n - k = 0 but I don't see how this can help and why you can do this?

You should have some initial condition T(1) = b for some constant b. Then T(2^k) = b + kc. If n = 2^k, then k = log(n) (logarithm to the base 2). Therefore, T(n) = b + c*log(n) = O(log(n)).

When n is not a power of 2, then the solution depends on whether / is regular division or integer division (which throws away the remainder). In the first case, you need more initial conditions to define T(n) for all n; in fact, you need to know T(n) for all odd natural numbers n. In the second case, I think you can prove that T(n) is monotonic (not necessarily strictly) and you can still have the O(log(n)) bound.