title: Time complexity of recursive algorithms with branches of different complexity
body: <p>I have the algorithm</p>
  
  <pre><code>def alg(a):
      if a == 0:
          return 1
      elif a % 2 == 1:
          return alg(a - 1)
      else:
          return alg(a / 2)
  </code></pre>
  
  <p>and am not certain what its complexity is. One branch has complexity of O(N) and the other O(log(N)).</p>
  
  <p>Do you in this case say that the algorithm has complexity of O(N) since that is the worse case or is the complexity something completely different in this case?</p>