Recall that the Cartesian product $A\times A$ is defined as the set $\lbrace (x,y):x\in A ,y \in A \rbrace$ . Thus, if for example, $A=\lbrace 1,2,3 \rbrace$,$A \times A=\lbrace(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)\rbrace$, then the time complexity is $O(n^2 \log n)$, where n refers to the number of members of the set (I presume). But suppose I would like to evaluate $A \times A \times A$ or any finite number of sets in $A \times A \times A$... What would the time complexity be then?
Asked
Active
Viewed 2,640 times
1
-
If I may ask, what use-case do you have in mind? quantifying the time complexity of the cartesian product seems odd, so I'm using the ##math IRC guidelines to understand why you need this :) – Siddharth Bhat Feb 10 '20 at 18:09
1 Answers
1
I assume the task is generating a string representation of $A^k$.
If $A$ has $n$ elements, we have to list $n^k$ tuples with $k$ components each.
However the size of the numbers themselves grows with growing $n$, needing about $\log_{10}(n) + 1$ digits per component.
So that will give an output of roughly $n^k k \log_{10} n$ digits.
mvw
- 34,562
-
Again, thank you for the response. My only other question is if this is considered "fast" to compute. Is it faster or slower than polynomial time? – Carl Hill Jul 04 '15 at 01:42
-
The number of digits seems to be $O(n^{k+1})$ so needing polynomial time. Yes that is fast in quotes. – mvw Jul 04 '15 at 06:48