Databases
StackOverflow2013
Postsdbo
POHomework: finding Big-Oh for code fragments
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHomework: finding Big-Oh for code fragments
    primarykey
    data
    text
    <p>To be up front with everyone, this is for a homework assignment. I don't expect anyone to provide out and out answers for me, this is more to check that I'm understanding things correctly or to figure out what I'm doing wrong.</p> <p>I've been given some fragments of code to determine what Big-Oh would be of them. Each is dealing with for loops, however the last two that we were given are throwing me off a bit. The first:</p> <pre><code> sum = 0; for (i = 0; i &lt; n; i++) //1 for (j = 0; j &lt; i * i; j++) //2 for (k = 0; k &lt; j; k++) //3 sum++; </code></pre> <p>I think that Big-Oh of this would be O(n^4). #1 will run n times, #2 will run n^2 times, and #3 will run n times, giving me n^4. However, when I write this properly in C++ and give n values of 10, 100 and 1000 (per my assignment), n = 10 returns 7524 (good, less than 10,000) n = 100 returns a value of 975,002,490 while the upper bound would be 100,000,000. Obviously, I'm off somewhere in my analysis of the loops, but I'm not quite sure where. Not sure what n = 1000 will return, since my computer has been crunching away at it for a while and doesn't appear to be ready to give me an answer yet.</p> <p>The second fragment is as follows:</p> <pre><code> sum = 0; for (i = 0; i &lt; n; i++) //1 for (j = 0; j &lt; i * i; j++) //2 if (j % i == 0) //3 for (k = 0; k &lt; j; k++) //4 sum++; </code></pre> <p>I believe I can safely ignore the if statement since its runtime would be the running time of the test plus its contents, meaning I would again come up with O(n^4).</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. This table or related slice is empty.
    1. USRon Holcomb
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. COIf the j loop is supposed to run n^2 times according to your analysis, wouldn't the k loop also run n^2 times by the same argument? Asymptotic analysis always ignores the constant factors for the most part, which might be an issue in realistic scenarios.
      singulars
      1. POHomework: finding Big-Oh for code fragments
      1. USAmbidextrous
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload