title: Determining the big-O runtimes of these different loops?
body: <p>I have a series of questions in which I need feedback and answers. I will comment as to what I think, this is not a homework assignment but rather <strong>preparation</strong> for my exam.</p>
  <p>My main problem is determining the iterations of a loop for different cases. How would go about attempting to figure that out?</p>
  <p>Evaluate Running time.</p>
  <p>Q2.</p>
  <pre><code> for(int i =0 ; i &lt; =n ; i++) // runs n times
     for(int j =1; j&lt;= i * i; j++) // same reasoning as 1. n^2
        if (j % i == 0)
           for(int k = 0; k&lt;j; k++) // runs n^2 times? &lt;- same reasoning as above.
              sum++;
  </code></pre>
  <p><strong>Correct Answer: N × N2 × N = O(N^4)</strong></p>
  <p>For the following Questions below, I do not have the correct answers.</p>
  <p>Q3. a)</p>
  <pre><code>     int x=0; //constant
       for(int i=4*n; i&gt;=1; i--) //runs n times, disregard the constant
           x=x+2*i;
  </code></pre>
  <p>My Answer: O(n)</p>
  <p>b) Assume for simplicity that n = 3^k</p>
  <pre><code>    int z=0;
      int x=0;
      for (int i=1; i&lt;=n; i=i*3){ // runs n/3 times? how does it effect final answer?
         z = z+5;
         z++;
         x = 2*x;
      }
  </code></pre>
  <p>My Answer: O(n)</p>
  <p>c) Assume for simplicity that n = k^2,</p>
  <pre><code>   int y=0; 
     for(int j=1; j*j&lt;=n; j++) //runs O(logn)?  j &lt;= (n)^1/2
     y++; //constant
  </code></pre>
  <p>My Answer: O(logn)</p>
  <p>d)</p>
  <pre><code>  int b=0; //constant
    for(int i=n; i&gt;0; i--) //n times
      for(int j=0; j&lt;i; j++) // runs n+ n-1 +...+ 1. O(n^2) 
        b=b+5;
  </code></pre>
  <p>My Answer: O(n^3)</p>
  <p>(e)</p>
  <pre><code> int y=1;
   int j=0;
   for(j=1; j&lt;=2n; j=j+2) //runs n times
      y=y+i;
   int s=0;
   for(i=1; i&lt;=j; i++) // runs n times
   s++;
  </code></pre>
  <p>My Answer: O(n)</p>
  <p>(f)</p>
  <pre><code> int b=0;
   for(int i=0; i&lt;n; i++) //runs n times
     for(int j=0; j&lt;i*n; j++) //runs n^2 x n times? 
        b=b+5;
  </code></pre>
  <p>My Answer: O(n^4)</p>
  <p>(g) Assume for simplicity that n = 3k, for some positive integer k.</p>
  <pre><code>   int x=0;
     for(int i=1; i&lt;=n; i=i*3){  //runs 1, 3, 9, 27...for values of i. 
       if(i%2 != 0) //will always be true for values above
        for(int j=0; j&lt;i; j++) // runs n times
          x++;
      }
  </code></pre>
  <p>My Answer: O (n x log base 3 n? )</p>
  <p>(h) Assume for simplicity that n = k2, for some positive integer k.</p>
  <pre><code>   int t=0;
     for(int i=1; i&lt;=n; i++) //runs n times
        for(int j=0; j*j&lt;4*n; j++) //runs O(logn)
           for(int k=1; k*k&lt;=9*n; k++) //runs O(logn)
              t++;
  </code></pre>
  <p>My Answer: n x logn x log n = O(n log n^2)</p>
  <p>(i) Assume for simplicity that n = 2s, for some positive integer s.</p>
  <pre><code>   int a = 0;
     int k = n*n;
       while(k &gt; 1) //runs n^2
       {
         for (int j=0; j&lt;n*n; j++) //runs n^2
            { a++; }
          k = k/2;
      }
  </code></pre>
  <p>My Answer: O(n^4)</p>
  <p>(j)</p>
  <pre><code>  int i=0, j=0, y=0, s=0;
    for(j=0; j&lt;n+1; j++) //runs n times
       y=y+j; //y equals n(n+1)/2 ~ O(n^2)
    for(i=1; i&lt;=y; i++) // runs n^2 times
       s++;
  </code></pre>
  <p>My Answer: O(n^3)</p>
  <p>(k)
  int i=1, z=0;
  while( z &lt; n*(n+1)/2 ){  //arithmetic series, runs n times
  z+=i; i++;
  }</p>
  <p>My Answer: O(n)</p>
  <p>(m) Assume for simplicity that n = 2s, for some positive integer s.</p>
  <pre><code>  int a = 0;
    int k = n*n*n;
    while(k &gt; 1) //runs O(logn) complexity
     {
       for (int j=0; j&lt;k; j++) //runs n^3 times
        { a--; }
       k = k/2; 
      }
  </code></pre>
  <p>My Answer: O(n^3 log n)</p>
  <p><strong>Question 4</strong></p>
  <p><img src="https://i.stack.imgur.com/zMkt7.jpg" alt="The question in this image" /></p>
  <ul>
  <li>a) True - since its bounded below by n^2</li>
  <li>b) False - f(n) not strictly smaller than g(n)</li>
  <li>c) True</li>
  <li>d) True -bounded by n^10</li>
  <li>e) False - f(n) not strictly smaller than g(n)</li>
  <li>f) True</li>
  <li>g) True</li>
  <li>h) false - since does not equal O(nlogn)</li>
  <li>i) true</li>
  <li>j) not sure</li>
  <li>k) not sure</li>
  <li>l) not sure - how should i even attempt these?*</li>
  </ul>
  <p>Thanks in advance.</p>