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
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
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
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
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
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
Note: The fact that the algorithm has better performance, with the same
worst case complexity does not imply that the average complexity was