“let’s assume that the time taken is a sum of products”
This is the definition of a polynomial, although you might not have intended it to be a polynomial in something other than the input dimensions. In that case, I’m not sure I’ve understood clearly what you are arguing.
I was making the point that if the run time can be broken down in a form where it’s expressed as a sum of products, where the summands are the times taken for some sub-algorithms, then we can attempt to tweak the sub-algorithms to reduce the time taken for the individual tasks.
The time taken for the sub-algorithm may or may not be polynomial in the input dimensions.
“let’s assume that the time taken is a sum of products”
This is the definition of a polynomial, although you might not have intended it to be a polynomial in something other than the input dimensions. In that case, I’m not sure I’ve understood clearly what you are arguing.
Sorry for my lack of clarity.
I was making the point that if the run time can be broken down in a form where it’s expressed as a sum of products, where the summands are the times taken for some sub-algorithms, then we can attempt to tweak the sub-algorithms to reduce the time taken for the individual tasks.
The time taken for the sub-algorithm may or may not be polynomial in the input dimensions.
Ok.