# Recurrency equation, algorithms, complexity

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 :)

• You're almost there. Use the fact that $1+2+\dotsm+k=k(k+1)/2$ and realize that $k=\lg n$. Oct 13 '16 at 14:52
• yep that's true, then I'm left with something like: $$T(N) = c[((lg n)^2 + lg n) / 2] + 1$$ And I'm not sure but can I simply say that $$T(N) = Omega((lg n)^2 / 2)$$ ? Oct 13 '16 at 15:02