Search code examples
algorithmrecurrence

How to solve T(n) = T(0.2*n^0.5) + 1?

I know how to solve T(n) = T(n^0.5) + 1. Let m = lg n and S(m) = T(2^m). We then get S(m) = S(m/2) + 1. And we know S(m) = Θ(lg m). So T(n) = Θ(lg lg n).

However I'm not sure how to solve T(n) = T(0.2*n^0.5) + 1. The 0.2 is throwing me off. If I use the same method, I'm not sure how to figure out what S(m) is.

Solution

  • On the new one, you get

    S(lg n) = S(lg 0.2 + 0.5 lg n) + 1
S(m) = S(lg 0.2 + 0.5 m) + 1.

    The trick is to substitute R(x) = S(m + 2 lg 0.2).

    R(x) = S(m + 2 lg 0.2)
     = S(lg 0.2 + 0.5 (m + 2 lg 0.2)) + 1
     = S(0.5 m + 2 lg 0.2) + 1
     = R(0.5 x) + 1

    Then unravel the substitutions and conclude that T(n) = Theta(lg lg n), as before.