title: solution of recurrence relations of a program
body: <p>I have a quiz which asked me to work out the solution of a recurrence relation of a program:</p>
  
  <p>The amount of time,T(n) taken by an algorithm is typically a function of the size,
  n, of the input data. Assume that you wrote a program that shows the following time recurrence:</p>
  
  <blockquote>
    <p>T(n) = T(n/2) + a , if n > 1</p>
    
    <p>T(n) = b, if n= 1</p>
  </blockquote>
  
  <p>Here is what I have tried:</p>
  
  <blockquote>
    <p>T(n/2) = T(n/4) + a 
    T(n/4) = T(n/8) + a</p>
  </blockquote>
  
  <p>So:</p>
  
  <blockquote>
    <p>T(n) = T(n/4) + 2*a = T(n/8) + 3*a = T(n/K) + 3*a</p>
  </blockquote>
  
  <p>Up to here, I want to make T(n) = 1 which the program should be terminated, so I make </p>
  
  <blockquote>
    <p>n/K = 1 -> K = n</p>
  </blockquote>
  
  <p>And i get:</p>
  
  <blockquote>
    <p>T(n/n) + 3*a = b + 3a</p>
  </blockquote>
  
  <p>However the answer shows this program have a Logarithmic complexity and the solution should be T(n) = a ∗ log2(n) + b</p>
  
  <p>I do not understand how to get the above solution, can anyone help me?
  Thank you!</p>