Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p><a href="http://en.wikipedia.org/wiki/Matrix_multiplication" rel="nofollow noreferrer">Matrix multiplication</a> has a theoretical lower bound of Ω(<em>n</em><sup>2</sup>), since all <em>n</em><sup>2</sup> entries need to be processed. The best known algorithm to date (according to the above-linked Wikipedia article) has complexity O(<em>n</em><sup>2.3727</sup>). The naive algorithm has complexity <em>n</em><sup>3</sup>.</p> <p>According to the Wikipedia article on <a href="http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations" rel="nofollow noreferrer">Computational complexity of mathematical operations</a>, back-substitution of a triangular matrix to obtain <em>n</em> solutions is O(<em>n</em><sup>2</sup>). There are probably many other examples around on the web.</p> <p>EDIT: A 2014 <a href="https://arxiv.org/pdf/1407.4972.pdf" rel="nofollow noreferrer">paper by Michele Borassi, <em>et al.</em></a>, discusses a number of decision problems (output size O(1)) that can be solved in O(<em>n</em><sup>2</sup>) time but not in O(<em>n</em><sup>2-<em>ε</em></sup>) for any <em>ε</em> > 0. (Of course, as always, these results depends on P ≠ NP, or, more precisely, that the <a href="https://en.wikipedia.org/wiki/Exponential_time_hypothesis" rel="nofollow noreferrer">Strong Exponential Time Hypothesis</a> is true.)</p> <p>Their paper leads off with a modified <a href="https://en.wikipedia.org/wiki/Boolean_satisfiability_problem" rel="nofollow noreferrer"><em>k</em>-SAT problem</a>:</p> <p><em>Input:</em></p> <ul> <li>two sets of variables <em>X</em> = {<em>x</em><sub><em>i</em></sub>}, <em>Y</em> = {<em>y</em><sub><em>j</em></sub>} of the same size;</li> <li>a set <em>C</em> of clauses over these variables, such that each clause has at most size <em>k</em>; and</li> <li>the two power sets &weierp;(<em>X</em>), &weierp;(<em>Y</em>) of <em>X</em> and <em>Y</em> (used to change the input size).</li> </ul> <p><em>Output:</em> <code>true</code> if there is an evaluation of all variables that satisfies all clauses, <code>False</code> otherwise.</p> <p>Note that the unmodified <em>k</em>-SAT problem (where the input does not include the third bullet above) is NP-complete, so normally one thinks of it as an exponential-time problem. However, here the input size is itself exponential in the number of variables. They show that, with this modification, the problem can always be solved in quadratic time (simply try all possible evaluations). More to the point for this answer, they also show that this is the minimum time complexity for any algorithm that solves the problem.</p> <p>One might object that this modified <em>k</em>-SAT problem is hardy natural. However, they then use this to show that a number of other problems, which do seem natural, also cannot be solved in less that O(<em>n</em><sup>2</sup>) time. The simplest one to state is the subset graph problem:</p> <p><em>Input:</em> a set <em>X</em> and a collection <em>C</em> of subsets of <em>X</em>.</p> <p><em>Output:</em> the graph <em>G</em> = (<em>C</em>, <em>E</em>), where, for each <em>C</em>, <em>C</em>′ ∈ <em>C</em>, (<em>C</em>, <em>C</em>′) ∈ <em>E</em> if and only if <em>C</em> ⊆ <em>C</em>′.</p>
    singulars
    1. This table or related slice is empty.
    1. POAlgorithmic task which requires quadratic time?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USTed Hopp
    1. USTed Hopp
    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. COThat is not correct. In formal complexity theory, Run-time is a function of input size. It takes n^2 size to represent an nxn matrix. So the lower bound is in fact linear.
      singulars
      1. PO
      1. USakashnil
    2. CO@akashnil - Yeah, I thought about that. However, I'm just going with the standard terminology used in the literature.
      singulars
      1. PO
      1. USTed Hopp
    3. CO@akashnil - I take it back. Consider the outer product of two 1xn matrices. The input size is 2n (= O(n)). The output size is O(n^2). Theoretical complexity is O(n^2). Also, see my updated answer for another example.
      singulars
      1. PO
      1. USTed Hopp
 

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