I'm trying to solve recurrency equation and I fell like unnable to proceed my logic and math to finish it.
Until now I've sth like that:
$$T(1) = 1 $$
$$T(N) = c(lg N) + T(N/2)$$, where lg is a logarithm of base 2
$$lg N = k $$ $$2^k = N $$
$$T(N) = c(lg 2^k) + T((2^k/2)$$ $$T(N) = ck + T(2^k-1)$$ $$T(N) = ck + c(k-1) + c(k-2) + ... + c + T(2^k / 2^k)$$ $$T(N) = ck + c(k-1) + c(k-2) + ... + c + 1 $$ ...and from here I don't know how to nicely cut that formula to get the final result, I agree I'm quite bad at math cause that's not subject of my studies, thus any help will be really appreciated :)
Thanks in advance big minds!