1
$\begingroup$

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!

$\endgroup$
3
  • $\begingroup$ Do you have the Master Theorem available? If so, it is quickest just to plug into that (the middle case applies). $\endgroup$ Oct 13 '16 at 14:08
  • $\begingroup$ You're almost there. Use the fact that $1+2+\dotsm+k=k(k+1)/2$ and realize that $k=\lg n$. $\endgroup$ Oct 13 '16 at 14:52
  • $\begingroup$ 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)$$ ? $\endgroup$
    – kolboc
    Oct 13 '16 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.