6
$\begingroup$

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 ?

$\endgroup$
4
  • $\begingroup$ I changed your former title "How to compute the time-complexity of an optimized algorithm relative to the original algorithm ?". The reason is that it did not seem to make sense. The two complexities can be compared, but they are computed indpendently. --- --- Did you make sure that dealing with a smaller number of elements did not change the cost of dealing with one element? $\endgroup$
    – babou
    Jul 22, 2015 at 13:53
  • $\begingroup$ sorry, but I am unable to answer your question ... I don't know the meaning of cost or how to compute it ? $\endgroup$
    – user35624
    Jul 22, 2015 at 13:55
  • $\begingroup$ Cost is a generic term that you can replace by time, space, energy of whatever other cost measure you are considering when doing complexity analysis. So here, you may read it as "time complexity to process one element". $\endgroup$
    – babou
    Jul 22, 2015 at 13:59
  • 3
    $\begingroup$ It depends. How does $n$ relate to $h$? What's the smallest it could be, and the largest it could be? Same for $m$ and $w$. $\endgroup$
    – D.W.
    Jul 23, 2015 at 22:01

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ I can add that $n$ is almost equal to $w$ BUT $m$ is inferior to $h$ sometime by half, sometime by more. $\endgroup$
    – user35624
    Jul 22, 2015 at 13:56
  • $\begingroup$ As I said, constant factors will not change the complexity. You have to give a precise function of $u(h)$ which is an upperbound for $m$, i.e. $\forall h, m<u(h)$, and which grows less than any linear function. But improving the complexity is probably not your real worry. $\endgroup$
    – babou
    Jul 22, 2015 at 14:06
  • $\begingroup$ the relation between $h$ and $m$ (or even an upperbound) is very impredictible. So even if the worst-case time-complexity may be the same. the running performance can be better ? $\endgroup$
    – user35624
    Jul 22, 2015 at 14:48
  • 2
    $\begingroup$ @OSryx YES, the running performance can be better It can be a zillion times better without changing the complexity. Suppose you do not trust your computer, so you do every computation twice on the same input to double check the first answer against stray cosmic rays. Your algorithm will be twice as slow. But your complexity will be exactly the same. $\endgroup$
    – babou
    Jul 22, 2015 at 15:00
2
$\begingroup$

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.

$\endgroup$
13
  • $\begingroup$ Interesting ... $m$ is near $w$ but $h=c\times n$. So the time complexity in worst case is not optimized since constant $c$ can be equal 1. But the time complexity in average maybe $c=1/2$ !! I have to consider to compute the tc in average case. What is the symbol ? It is not big-o ? UPVOTE $\endgroup$
    – user35624
    Jul 21, 2015 at 22:00
  • $\begingroup$ It is still big-oh. Big-oh can be used in discussion of any asymptotic complexities, but you should mention the exact use (if it is not clear from context). For instance, in parallel algorithms you must specify the work and time complexities. Look at a discussion of quick sort for an example of an average-case vs. worst-case complexities. $\endgroup$
    – Kittsil
    Jul 21, 2015 at 22:07
  • $\begingroup$ I do not see why "before [the] optimization, the algorithm had the same worst- and average-case complexity". The question does not even say what kind of complexity is being considered. I do not see either why you assume (seemingly) that the optimizations improved the average case complexity. $\endgroup$
    – babou
    Jul 22, 2015 at 14:10
  • $\begingroup$ @babou The question implies that the unimproved algorithm always takes $O(w \times h)$; hence, the average- and worst-cases are the same. I assume that the time is improved in at least some cases, because otherwise (s)he would not have asked the question. $\endgroup$
    – Kittsil
    Jul 22, 2015 at 15:12
  • 2
    $\begingroup$ @OSryx See here for a quick introduction into which Landau symbol to use when. $\endgroup$
    – Raphael
    Jul 24, 2015 at 5:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.