title: Cannot understand CLRS Problem 4-2 case 2
body: <p>The question:</p>
  
  <blockquote>
    <p><strong>4-2 Parameter-passing costs</strong></p>
    
    <p>Throughout this book, we assume that parameter passing during procedure calls takes constant time, even if an N-element array is being passed. This assumption is valid in most systems because a pointer to the array is passed, not the array itself.
    This problem examines the implications of three parameter-passing strategies:</p>
    
    <ol>
    <li>An array is passed by pointer. Time Theta(1)</li>
    </ol>
    
    <p><strong>2. An array is passed by copying. Time Theta(N), where N is the size of the array.</strong></p>
    
    <ol start="3">
    <li>An array is passed by copying only the subrange that might be accessed by the called procedure. Time Theta(q-p+1) if the subarray A[p..q] is passed.</li>
    </ol>
    
    <p>a. Consider the recursive binary search algorithm for finding a number in a sorted array (see Exercise 2.3-5 ). Give recurrences for the worst-case running times of binary search when arrays are passed using each of the three methods above, and give good upper bounds on the solutions of the recurrences. Let N be the size of the original problem and n be the size of a subproblem.</p>
    
    <p>b. Redo part (a) for the MERGE-SORT algorithm from Section 2.3.1.</p>
  </blockquote>
  
  <p>I have trouble understanding how to solve the recurrence of case 2 where arrays are passed by copying for both algorithms.</p>
  
  <p>Take the binary search algorithm of case 2 for example, the recurrence most answers give is <strong>T(n)=T(n / 2)+Theta(N)</strong>. I have no trouble about that.</p>
  
  <p>Here is an answer I find online that looks correct:</p>
  
  <blockquote>
    <p>T(n)</p>
    
    <p>= T(n/2) + cN</p>
    
    <p>= 2cN + T(n/4)</p>
    
    <p>= 3cN + T(n/8)</p>
    
    <p>= Sigma(i = 0 to lgn - 1) (2^i cN / (2^i))</p>
    
    <p>= cNlgn</p>
    
    <p>= Theta(nlgn)</p>
  </blockquote>
  
  <p>I have trouble understanding how the second last line can result in the last line's answer. Why not represent it in Theta(Nlgn)? And how can N become n in the Theta notation?</p>
  
  <p>N and n feel somewhat connected. I have trouble understanding their connection and how that is applied in the solution.</p>