title: Master Method: Divide and Conquer
body: <p>According to my  evaluation the overall asymptotic running time of the  below algorithm is <code>O(n) </code> ,since  <code>x</code> (number of recursions) is 1, and <code>y</code> is  ( the number of splits) is 2  , and finally <code>z</code>  ( the power  of of amount of work done outside of the recursion call) is 1, hence x&lt;y^{d}, but my answer is wrong . Why?</p>
  <pre><code>    FastPower(a,b) :
      if b = 1
        return a
      else
        c := a*a
        ans := FastPower(c,[b/2])
      if b is odd
        return a*ans
      else return ans
    end
  </code></pre>