Linear time algorithm to compute cartesian product
There are mn results; the minimum work you have to do is write each result to the output. So you cannot do better than O(mn).
I was asked in an interview to come up with a solution with linear time for cartesian product. I did the iterative manner O(mn) and a recursive solution also which is also O(mn). But I could not reduce the complexity further. Does anyone have ideas on how this complexity can be improved? Also can anyone suggest an efficient recursive approach?