How to compare the time-complexity of an optimized algorithm with that of the original?

Question

I had an algorithm with time-complexity of $O(h\times w)$, knowing $h$ is the height and $w$ is the width of an image being processed (or a simple matrix of size $h\times w$).

I managed to reduce the range that the algorithm process. So rather than dealing with $h\times w$ elements, it is dealing with $n\times m$ elements, where $n<h$ and $m<w$.

To recapitulate the optimization :

• Time-complexity of old algorithm is $O(h\times w)$
• Time-complexity of new algorithm is $O(h) + O(n\times m)$

Now my question is : how to express this time complexity optimization in terms of $h$ and $w$ ? is it a real optimization ?

Answer 1

I am not sure what you mean by "complexity optimization".

A proper way to compare complexities is by considering their ratio, which is defined up to a constant factor. Considering the difference makes no sense, as there is always the invisible constant factor lurking around, invisible but not negligible.

However your problem here is that you have several variables, not the same in both variants of your algorithm, and no indication of how they relate. If you do not say precisely how $n$ and $m$ relate to $h$ and $w$, there is nearly nothing that can be done.

Given That all you know is that $n<h$ and $m<w$, the best you can say is that $n\times m<h\times w$. But they may differ by a constant additive term or by a constant multiplicative factor, which does not change the complexity.

So the best you can say is that $O(m\times n)\subseteq O(h\times w)$, short of more precision on how $n$ and $m$ relate to $h$ and $w$

Thus $O(h)+O(m\times n)\subseteq O(h)+O(h\times w)$.

But $O(h)\subseteq O(h\times w)$, because both are linear in $h$ and the first is constant in $w$ while the second is linear.

Hence you get: $O(h)+O(m\times n)\subseteq O(h\times w)$.

All we know is that the complexity is not worse than before.

But that should not worry you too much. You seem to have the wrong vision of complexity, when asking:

is it a real optimization ?

Your optimizations aim at improving performance in your range of applications.

Complexity does not measure performance but scalability. A constant multiplicative factor of ten zillions does not change the complexity but has a drastic effect on performance. The matrix multiplication algorithm that have the best complexity are never used because they have abysmal performance. You have to consider huge matrices for them to be any use.

Furthermore, raw complexity on arbitrary measure of the size of the problem may have little practical meaning in some cases. The relevant size for some complexity analyses may be the number of occurences of a specific feature of the problem input, rather than the length of the problem in number of symbols. Some exponential algorithms are routinely used without problems because the feature causing the high complexity is actually rarely used, independently of the input size.

Your modification of the algorithm may be a real optimization, that may give you an algorithm ten times faster, but this may not show in complexity analysis.

This is why it is sometimes useful to do precise cost analysis. But that is more difficult since you must account for the different costs of different elementary operations (which is not required for complexity analysis).

A possible way to assess your optimization is benchmarking, rather than tedious theoretical counting.

Your question did not say whether you were considering worst case or average complexity. I did not ask because my remarks apply in both cases.

Note: The fact that the algorithm has better performance, with the same worst case complexity does not imply that the average complexity was improved.

Answer 2

It appears that, before your optimization, your algorithm had the same worst- and average-case complexity, which is why it was easy to consider.

The change in asymptotic complexity really depends on how $n$ and $m$ relate to $w$ and $h$. If they are reduced by a constant factor, then your asymptotic complexity is not improved. If they are some root or logarithmic function, then your complexity has improved.

"[If the asymptotic complexity is the same,] is this a real optimization?"

Yes! Anything you can do that improves the average case without (or rarely) hurting the worst case, even if the improvement is only by a constant factor, makes the algorithm more useful in real world problems. 4x might be a constant improvement, but if you can make me run 4x faster, I'll be ecstatic. As @babou states in his answer, the asymptotic complexity is only useful in studying how the running time changes with a change in input size.