Example 3 - Computing Complexities

Given: database consisting of one binary relation G and three queries:

1. cross (G) = ¶₁(G) X ¶₂(G)

2. path (G) = {(x,y) | x and y are connected by a path in G}

3. self (G) = G

cross VS. path:

Clearly, cross is "easier" than path - the complexity of the recognition problem for cross is O(n), and the complexity of the recognition problem for path is O(n²). But, the time complexity of constructing the result is O(n²) for both.

cross VS. self:

The complexity of the recognition problem is in both cases O(n), but the complexity of computing the result for self is O(n) and O(n²) for cross.

Back    Table of content