Recurrence Relations

213 Views Asked by At
        Base Case: T(1) = 0;        


        T(n) = 1 + T(N/2)

        plug = 1 + 1(1 + T(N/4))

        chug = 2 + T(N/4)

        plug = 2 + 1 (1 + T(N/8))

        chug = 3 + T(N/8)

        plug = 3 + 1 (1 + T(N/16))

        chug = 4 + T(N/16)

        pattern = i + T(N/2^i)


        N/2^i = 1

        2^i = N

        i = log_2(N)

        final equation : 

        log_(2)N + T(1)


        Conlusion : O(log_N)

I have tried solving the question, but I'm not sure whether the method i used was correct. Plz review.