Search code examples
divide-and-conquerrecurrencemaster-theorem

Recurrence relationship

Can anyone help in solving the recurrence relationship of a divide and conquer algorithm with the following equation? I am pretty sure you can't use master theorem here because it is not in the form T(n/b) but may be forgetting a simple math rule here. Please help.

T(n)=T(√n)+logn.

Solution

  • Notice that for some k>0 we have

    T(n) = log n + log n^{1/2} + log n^{1/4} + ... + log n^{1/2^k} =
     = log n + (1/2)*log n + (1/4)*log n + ... + (1/k) * log n
     = (1 + 1/2 + 1/4 + ... + 1/2*k) log n
     = (1 + 2^{-1} + 2^{-2} + ... + 2^{-k})log n
     <= 2 log n

    from which it follows that T(n) = O(log n). The bound <= 2 log n follows because 1+1/2+1/4+1/8+1/16+...=2 in the limit.