title: Homework - Big O analysis
body: <p>My homework involves Big O analysis and I think I've got the hang of it, but I'm not 100% sure. Would any of you lovely people mind taking a look and telling me if I'm on the right track?</p>
  
  <p>The assignment is below. For questions 1 and 3, my analysis and answers are on the right, after the // marks. For question 2, my analysis and answers are below the algorithm type.</p>
  
  <p>Thanks in advance for your help! :-)</p>
  
  <pre><code>1.For each of the following program fragments, give a Big-Oh analysis of the running time in terms of N:
      (a) // Fragment (a)
          for ( int i = 0, Sum = 0; i &lt; N; i++ )      // N operations
              for( int j = 0; j &lt; N; j++ )            // N operations
                  Sum++;                              // Total: N^2 operations  =&gt;  O(N^2)
  
      (b) // Fragment (b)
          for( int i = 0, Sum = 0; i &lt; N * N; i++ )   // N^2 operations
              for( int j = 0; j &lt; N; j ++ )           // N operations
                  Sum++;                              // Total: N^3 operations  =&gt;  O(N^3)
  
      (c) // Fragment (c)
          for( int i = 0, Sum = 0; i &lt; N; i++ )       // N operations
              for( int j = 0; j &lt; i; j ++ )           // N-1 operations
                  Sum++;                              // Total: N(N-1) = N^2 – N operations  =&gt;  O(N^2)
  
      (d) // Fragment (d)
          for( int i = 0, Sum = 0; i &lt; N; i++ )       // N operations
              for( int j = 0; j &lt; N * N; j++ )        // N^2 operations 
                  for( int k = 0; k &lt; j; k++ )        // N^2 operations 
                      Sum++;                          // Total: N^5 operations  =&gt;  O(N^5)
  
  2. An algorithm takes 0.5 milliseconds for input size 100. How long will it take for input size 500 if the running time is:
      a. Linear
          0.5 *5 = 2.5 milliseconds
  
      b. O( N log N)  
          O (N log N) – treat the first N as a constant, so O (N log N) = O (log N)
          Input size 100 = (log 100) + 1 = 2 + 1 = 3 operations
          Input size 500 = (log 500) + 1= 2.7 + 1 = 3.7 ≈ 4 operations
          Input size 100 runs in 0.5 milliseconds, so input size 500 takes 0.5 * (4/3) ≈ 0.67 milliseconds
  
      c. Quadratic        
          Input size 100 in quadratic runs 100^2 operations =   10,000 operations
          Input size 500 in quadratic runs 500^2 operations = 250,000 operations = 25 times as many
          Input size of 100 runs in 0.5 milliseconds, so input size of 500 takes 25 * 0.5 = 12.5 milliseconds
  
      d. Cubic
          Input size 100 in quadratic runs 100^3 operations =     1,000,000 operations
          Input size 500 in quadratic runs 500^3 operations = 125,000,000 operations = 125 times as many
          Input size of 100 runs in 0.5 milliseconds, so input size of 500 takes 125 * 0.5 = 62.5 milliseconds
  
  
  3. Find the Big-O for the following:
      (a) f(x) = 2x^3 + x^2 log x             // O(x^3)
      (b) f(x) = (x^4 – 34x^3 + x^2 -20)      // O(x^4)
      (c) f(x) = x^3 – 1/log(x)               // O(x^3)
  
  4. Order the following functions by growth rate: (1 is slowest growth rate; 11 is fastest growth rate)
  __6_ (a) N
  __5_ (b) √N
  __7_ (c) N^1.5
  __9_ (d) N^2
  __4_ (e) N log N
  __2_ (f) 2/N        
  _11_ (g) 2^N
  __3_ (h) 37
  _10_ (i) N^3
  __1_ (j) 1/ N^2
  __8_ (k) N^2 /log N
  
  
  * My logic in putting (j) and (f) as the slowest is that as N grows, 1/N^2 and 2/N decrease, so their growth rates are negative and therefore slower than the rest which have positive growth rates (or a 0 growth rate in the case of 37 (h)). Is that correct?
  </code></pre>