Linear time algorithm for calculating the Cartesian product

Question

I was asked in an interview to come up with a linear time solution for a Cartesian product. I made an iterative method of O (mn) and a recursive solution, which is also O (mn). But I could not reduce the complexity. Does anyone have any ideas on how this complexity can be improved? Also can anyone suggest an efficient recursive approach?

Answer 1

There are mn results; the minimal work you have to do is write each result to the output. So you cannot do better than O(mn) .

Answer 2

The question that comes to my mind reads this: "Linear with respect to what?" Remember that in mathematics, all variables must be defined as meaningful. Big-O is no exception. Just saying that the O (n) algorithm does not make sense if n is not defined.

Assuming the question was significant and not a mistake, I assume that they wanted you to ask for clarification. Another possibility is that they wanted to see how you would respond when presented with an impossible situation.