Cześć, mam do rozwiązania następujące równanie rekurencyjne z przedmiotu algorytmy i struktury danych:
T(n)=2T(n/2)+cn
T(1)=1
Za n podstawiam 2^k ^. T(n)=2T(2^k-1 ^)+2^ k^*c=2*(2T(2^ k-2^)+2^k ^*c)+2^ k^*c = 2^ 3^T(2^ k-3^)+2^k+2 ^*c+2^k+1^*c+2^k^*c ... za 3 w nawiasie podstawiam k, aby wyszło T(1) i wtedy podstawię 1... W tym punkcie nie wiem jak dalej ruszyć, nic nie wychodzi.. ktoś może pomóc,wyjaśnić?
poprawiona składnia, tag plain - msm