title: How to get O(n) from T(n) = T(n/2) + n?
body: <p>I know that with master theorem i'll have teta(n), but i'm trying to resolve the recurrence in other way like this:</p>
  
  <pre><code>T(n) = T(n/2) + n
  T(n) = T(n/4) + 2n
  T(n) = T(n/8) + 3n
  .
  .
  .
  T(n) = T(n/2^k) + kn
  k=logn -&gt; T(1) + **nlogn**
  </code></pre>
  
  <p>what's the problem?</p>