title: What is Order of Growth and How do you compute it?
body: <h2>Why I am asking this question</h2>
  <p>I have recently started reading Sicp, and I have worked
  my way through to <a href="http://www.sicp-book.com/book-Z-H-11.html#%_sec_1.2.3" rel="nofollow noreferrer">Section 1.2.3</a>.
  I am unable to understand some of the details of Order of Growth. Please bear with me and
  my overly long question. Please also note that I have never dealt with analyzing algorithms before.</p>
  <h2>What I read in Sicp and my thoughts about it</h2>
  <p>Here are few pieces of the text from Sicp:</p>
  <h3>Which exact value is <em>n</em> ?</h3>
  <blockquote>
  <p>Let <em>n</em> be a  parameter that measures the size of the problem. In our previous examples we took n to be the number for which a given
  function is to be computed, but there are other possibilities. For instance,
  if our goal is to compute an approximation to the square root of a number,
  we might take n to be the number of digits accuracy required.</p>
  </blockquote>
  <p>Take the following procedure which was given in <a href="http://www.sicp-book.com/book-Z-H-4.html#%_toc_%_sec_1.1.7" rel="nofollow noreferrer">Section 1.7</a> for Newton's Method for Square roots:</p>
  <pre class="lang-lisp prettyprint-override"><code>(define (sqrt x)
    (sqrt-iter 1.0 x))
  </code></pre>
  <p>And this is <code>(sqrt-iter)</code></p>
  <pre class="lang-lisp prettyprint-override"><code>(define (sqrt-iter guess x)
    (if (good-enough? guess x)
        guess
        (sqrt-iter (improve guess x)
                   x)))
  </code></pre>
  <p>Where <code>good-enough?</code> checks if the <code>guess</code> a good enough approximations</p>
  <pre class="lang-lisp prettyprint-override"><code>(define (good-enough? guess x)
    (&lt; (abs (- (square guess) x)) 0.001))
  </code></pre>
  <p>Now, according to Sicp, <code>0.001</code> should be <code>n</code>, but shouldn't <code>n</code> be input in <code>(sqrt x)</code>?
  The number of iterations changes based on input <code>x</code>, that is the number of iterations required
  would change based on the size of the number.</p>
  <p>Here is my python equivalent proving that:</p>
  <pre class="lang-py prettyprint-override"><code>In [33]: sqrt(2)
  1
  1.5
  1.4166666666666665
  achieved 1.4142156862745097 in 3 iterations
  
  In [34]: sqrt(4)
  1
  2.5
  2.05
  2.000609756097561
  achieved 2.0000000929222947 in 4 iterations
  
  In [35]: sqrt(1024)
  1
  512.5
  257.2490243902439
  130.61480157022683
  69.22732405448895
  42.00958563100827
  33.19248741685438
  32.02142090500024
  achieved 32.0000071648159 in 8 iterations
  </code></pre>
  <p>So shouldn't <code>0.001</code> be <em>k1</em> or <em>k2</em>, as it is a value that is constant and is independent of
  <em>n</em> (here the value we input to <code>sqrt</code>)?</p>
  <h3>Isn't <em>R(n)</em> not constant?</h3>
  <blockquote>
  <p>let <em>R(n)</em> be the amount of resources the process requires for a problem of size <em>n</em>. <em>R(n)</em> might
  measure the number of internal storage registers used, the number of elementary machine operations performed, and so on. In computers that
  do only a fixed number of operations at a time, the time required will be
  proportional to the number of elementary machine operations performed.</p>
  </blockquote>
  <p>Here, Sicp says that <em>R(n)</em> might be the number of elementary operations performed, but
  isn't the number of operations performed be different from OS to OS? As a Linux Machine might
  do it a certain set of steps, a FreeBSD machine another, and a Windows Machine another?
  You'll see why I am saying this soon.</p>
  <h3>Order of Growth</h3>
  <blockquote>
  <p>We say that <em>R(n)</em> has order of growth <em>Θ(f (n))</em>, written <em>R(n) = Θ(f (n))</em> (pronounced “theta of f (n)”), if there are positive constants <em>k1</em> and <em>k2</em> independent of n such that <em>k1 f (n) ≤ R(n) ≤ k2 f (n)</em> for any sufficiently large value
  of n. (In other words, for large <em>n</em>, the value <em>R(n)</em> is sandwiched between
  <em>k1 f (n)</em> and <em>k2 f (n)</em>.)</p>
  </blockquote>
  <p>Now, from what I understand we calculate the growth of the resources used by doing some algebra after
  receiving the values from functions <code>R(n)</code> and <code>f(n)</code> (Is <em>R</em> a function? and <em>f</em> what I am thinking of? I don't know!)</p>
  <h3>The Example with Factorials and the Fibonacci Sequence</h3>
  <blockquote>
  <p>For instance, with the linear recursive process for computing factorial
  described in Section 1.2.1 the number of steps grows proportionally to the
  input n. Thus, the steps required for this process grows as Θ(n). We also
  saw that the space required grows as Θ(n). For the iterative factorial, the
  number of steps is still Θ(n) but the space is Θ(1)—that is, constant. The
  tree-recursive Fibonacci computation requires Θ(ϕn) steps and space Θ(n),
  where ϕ is the golden ratio described in Section 1.2.2.</p>
  </blockquote>
  <p>Now this is the part which makes no sense to me - what do I consider a step?
  Do I consider the number of substitutions using the substitution model?
  Or do I consider the number of expressions evaluated? Or do I consider when there
  is arithmetic evaluated?</p>
  <p>I understand that the the space is Θ(n) (because the interpreter needs to remember 1 more thing every recursion) in the recursive procedure and in the iterative Θ(1) (as the interpreter the some value with x and continues.) I don't understand how the Fibonacci computation (Tree Recursion) takes Θ(n).</p>
  <p>I also have no clue how the earlier <em>n</em> is related with the number of steps.</p>
  <h2>My Questions</h2>
  <p>So here is the list of all my questions to do with Order of Growth:</p>
  <ol>
  <li><p>Which exact value in an algorithm is n?</p>
  </li>
  <li><p>What happens in <em>R(n)</em>? (Assuming its a function of course) Does <em>n</em> divide/multiply a value?</p>
  </li>
  <li><p>What do I consider a step?</p>
  </li>
  <li><p>How do I compute the Order of Growth of the steps and space.</p>
  </li>
  </ol>
  <p>In short:</p>
  <p><strong>What is Order of Growth, and How do I compute it ?</strong></p>