I implemented an algorithm which takes a matrix of R rows and C columns as input.
I say that the worst case time complexity of the algorithm is
O(C√C * R^3) or O(C^1.5 * R^3)
Now someone asks me that can't it be denoted as simply O(R^3) for worst case.
I would say that since there are 2 inputs(not one) and sometimes C can be large and sometimes R can be large, so we cannot reduce it to simply O(R^3) and both C and R should be taken into account.
Is my answer correct? If not, why?
Yes, you are right, you cannot just simply ignore any of input parameters when considering the time complexity.
As C and R in both your case is unknown, we need to consider that they can be any values thus cannot ignore anything unless specified.
In your case as mentioned the time complexity must be specified as O(C^1.5 * R^3)
Now please notice that in your case that the time complexity is decided as product of variation of input parameters, thus even if it is specified that one parameter is strictly greater than other, we cannot just ignore that. Whereas in case of addition of complexities it can be ignored.
Just for example. If Input : R - any number C - any number >= R
In above case
O(R*C) = O(R*C) --> We Cannot just ignore any input parameter
O(R+C) = O(C) --> As we know C will always be greater than R
You are correct that C and R should be taken into account in your Big O expression.
Big O analysis is useful in situations where the size of your input may vary, and here the size of your input requires two parameters to describe since you say that "sometimes C can be large and sometimes R can be large".
The only way you could eliminate the C would be if C were O(1), in which case your function would grow as O(R^3), or if C were a function of R, e.g. if C = O(R), your function would grow as O(R^4.5).
