Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <h3> The methodology </h3> <p><hr> Okay. So you want to prove your algorithm's time complexity is <code>O(n^3)</code>. I understand why you would look at the time it takes for a program to run a calculation, but this data is not reliable. What we do, is we apply a weird form of <a href="http://en.wikipedia.org/wiki/Limit_%28mathematics%29" rel="nofollow">limits</a> to abstract away from the other aspects of an algorithm, and leave us with our <code>metric</code>.</p> <h3> The Metric </h3> <hr> <p>A <code>metric</code> is what we are going to use to measure your algorithm. It is the operation that occurs the most, or carries the most processing weight. In this case, it is this line:</p> <pre><code>value += mat1[m1Row][m1Column] * mat2[m2Row][m2Column]; </code></pre> <h3> Deriving the Recurrence Relation </h3> <p><hr> The next step, as I understand it, is to derive a recurrence relation from your algorithm. That is, a description of how your algorithm functions based on it's functionality in the past. Let's look at how your program runs.</p> <p>As you explained, you have looked at your three while loops, and determined the program is of order <code>O(n^3)</code>. Unfortunately, this is not mathematical. This is just something that seems to happen a lot. First, let's look at some numerical examples.</p> <p>When <code>m1RowLimit = 4, m2ColumnLimit = 4, innerLimit = 4</code>, our metric is ran <code>4 * 4 * 4 = 4^3</code> times. </p> <p>When <code>m1RowLimit = 5, m2ColumnLimit = 5, innerLimit = 5</code>, our metric is ran <code>5 * 5 * 5 = 5^3</code> times.</p> <p>So how do we express this in a recurrence relation? Well, using some basic maths we get:</p> <pre><code>T(n) = T(n-1) + 3(n-1)^2 + 3(n-1) + 1 for all n &gt;= 1 T(1) = 1 </code></pre> <p><h3> Solving the Recurrence Relation using Forward Substitution and Mathematical Induction </h3><hr> Now, is where we use some <a href="http://math.fullerton.edu/mathews/n2003/BackSubstitutionMod.html" rel="nofollow">forward substitution</a>. What we first do, is get a feel for the relation (this also tests that it's accurate).</p> <pre><code>T(2) = T(1) + 3(1^2) + 3(1) + 1 = 1 + 3 + 3 + 1 = 8. T(3) = T(2) + 3(2^2) + 3(2) + 1 = 8 + 12 + 6 + 1 = 27 T(4) = T(3) + 3(3^2) + 3(3) + 1 = 27 + 27 + 9 + 1 = 64 </code></pre> <p>NOW, we assert the hypothesis that T(n) = n^3. Let's test it for the base case:</p> <pre><code>T(1) = 1^3 = 1. // Correct! </code></pre> <p>Now we test it, using mathematical induction, for the next step. The algorithm increases by 1 each time, so the next step is: <code>T(n+1)</code>. So what do we need to prove? Well we need to prove that by increasing <code>n</code> by 1 on one side, the equal effect happens to <code>n</code> on the other. If it is true for all <code>n + 1</code>, then it is true for <code>n + 1 + 1</code> and so on. This means, we're aiming to prove that:</p> <pre><code>T(n + 1) = (n + 1)^3 T(n + 1) = T(n - 1 + 1) + 3(n + 1 - 1)^2 + 3(n + 1 - 1) + 1 = T(n) + 3(n)^2 + 3(n) + 1 Assume T(n) = n^3 T(n + 1) = n^3 + 3(n)^2 + 3(n) + 1 T(n + 1) = (n+1)^3 // Factorize the function. </code></pre> <p>So at this point, you've proven your algorithm has a run time complexity of <code>O(n^3)</code>.</p>
    singulars
    1. This table or related slice is empty.
    1. POHow can I estimate time complexity from a table of values?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USchristopher
    1. USchristopher
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POHow can I estimate time complexity from a table of values?
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COWow. VERY informative! Can we use this to calculate theta(N) and omega(N) as well?
      singulars
      1. PO
      1. USToni_Entranced
    2. COThat.. I must admit I'm not sure. Usually I just calculate big(O) and be done with it.
      singulars
      1. PO
      1. USchristopher
 

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