Search code examples
algorithmrecurrence

Computing for the closed form of a recurrence relation: Fractions

With the given: T(1) = 1

How would you compute for the closed form of T(n) = T(n/4) + 1?

The way I would answer this is:

T(n) = T(n/4) + 1
T(n) = T(n/8) + 1 + 1
T(n) = T(n/16) + 1 + 1 + 1

and so on. Is this the correct way of tackling with this equation? Am I missing some important key steps?

Solution

  • We have T(n)=T(n/4)+1

    Now find T(n/4) which is T(n/4)=T(n/(4^2))+1
    Therefore the 2nd term would be T(n)=T(n/(4^2))+2
    Similarly kth term would be T(n)=T(n/(4^k))+k
    Now put n=4^k in RHS of above equation, hence we get T(n)=T(1)+k
    => T(n)=1+k
    but n = 4^k
    => k = log n where base of log is 4.
    hence T(n)= (1+log n ); where base of log is 4.