How to find the time complexity of the algebra operation in algebraixlib

Question

How can I calculate time complexity using mathematics or Big O notation for algebra operations used in the algebra of data. I will use book example to explain my question. Consider following example given in book. B

In above example I would like to calculate the time complexity of transpose and compose operation.

If it possible I would also like to find out other algebra data operations' time complexity. Please let me know if you need more explanation.

@wesholler I edited my question to understand you explanation. Following is a real life example and suppose we want to calculate the time complexity for operations used below.

suppose I have algebra of data operations as follows

Could you describe how we would calculate the time complexity in above example. Preferably in Big O?

Thanks

Answer 1

This answer has three parts:

General Time Complexity Analysis

Generally, the time complexity/BigO can be determined by considering the origin of an operation - that is, what operations were extended from more primitive algebras to derive this one?

The following rules describe the upper-bound on the time complexity for both unary and binary operations that are extended into their power set algebras.

Unary extension can be thought of similarly to a map operation and so has linear time complexity. Binary extension evaluates the cross product of the operation's arguments and so has a worst-case time complexity similar to O(n^2). However it is important to consider that the real upper bound is a product of the cardinality of both arguments; this comes up in practice often when the right-hand argument to a composition or superstriction operation is a singleton.

Time Complexity for algebraixlib Implementations

We can take a look at a few examples of how extension affects the time complexity while at the same time analyzing the complexity of the implementations in algebraixlib (the last part talks about other implementations.)

Being that it is a reference implementation for data algebra, algebraixlib implements extended operations very literally. For that reason, Big Theta is used below, because the formulas represent both the lower and upper bounds of the time complexity.

Here is the unary operation transpose being extended from couplets to relations and then to clans.

Likewise, here is the binary operation compose being extended from couplets to relations and then to clans.

It is clear that the complexity of both of the clan operations is influenced by both the number of relation elements as well as the number of couplets in those relations.

Time Complexity for Other Implementations

It is important to note that the above section describes the time complexity that is specific to the algorithms implemented in algebraixlib.

One could imagine implementing e.g. clans.cross_union with a method similar to sort-merge-join or hash-join. In this case, the upper bound would remain the same, but the lower bound (and expected) time complexity would be reduced by one or more degrees.