Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p><strong>The first one is correct</strong>, and really well thought.</p> <hr> <p><strong>The second one is not</strong>. That algorithm to calculate fibs has much higher time complexity than O(n^4) (<strong>EDIT</strong>: <em>which was what was being asked when I wrote this answer -- the question has been updated meanwhile</em>). It is not even polynomial. The reasoning is as follows (notation #fib(x): number of times fib is called to calculate fib(x)):</p> <ul> <li>fib(1): #fib(1) = 1 (it returns directly the result)</li> <li>fib(2): #fib(2) = 3 (one for fib(2), which calls it for fib(0) and fib(1))</li> <li>fib(3): #fib(3) = 5 (one for fib(3), which calls it for fib(2) and fib(1), giving 3 + 1 more calls)</li> <li>fib(4): #fib(4) = 9</li> <li>fib(5): #fib(5) = 15</li> <li>fib(6): #fib(6) = 25</li> <li>...</li> <li>fib(i): #fib(i) = 1 + #fib(i-1) + #fib(i-2)</li> </ul> <p>So, you have:</p> <ul> <li>#fib(i) ~= #fib(i-1) + #fib(i-2)</li> </ul> <p>From this, it would be a reasonable guess that calculating fib(i) takes "about" (actually, just a little less than) 2 times the time to calculate fib(i-1). Hence, you could "guess" that O(#fib(i)) = O(2^i). This is the correct answer, which you can prove easily by induction.</p> <p>Just to finish about the Fibonacci Sequence, there are much faster algorithms to calculate the n-th number. For instance, an algorithm with linear time (ie, O(n)) is to memoize that function you wrote (ie, make it consult a Map to check if it know the result for n, is so return it immediately, otherwise, calculate it, store it and return it). There's also a <strong><a href="http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression" rel="nofollow">closed formula to calculate the n-th fib</a></strong>, therefore a constant-time algorithm (ie, O(1)).</p> <hr> <p>Finally, <strong>an example of O(n^4)</strong> algorithm is anything with 4 inner loops, each loop running "about" n times.</p> <p>For instance, calculate the volume of n cubes of side n (in a non-optimal way):</p> <pre><code>int volume = 0; for (int cube = 0; cube &lt; n; cube++) for (int x = 0; x &lt; n; x++) for (int y = 0; y &lt; n; y++) for (int z = 0; z &lt; n; z++) volume++; return volume; </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POJava Time Complexity O(n^2/3)
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USBruno Reis
    1. USBruno Reis
    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. 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. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COIt said 4^n, not n^4.
      singulars
      1. PO
      1. USLouis Wasserman
    2. CO@LouisWasserman, well noted. However, when I answered the question, it was asked about n^4, the OP changed it later, after I wrote this. Sorry for the inconvenience.
      singulars
      1. PO
      1. USBruno Reis
 

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