3

I have an algorithm that depending on the length of the input array and its values could take more or less operations to complete, for example, for a set with some length it could take 10.000 operations and for a set with same length but some different values could take 1.000.000 operations to process, of course the array length could change as it happens with its values.

I'm wondering how is the right way to express the time complexity for these kind of algorithms, maybe I'm not looking into the right location (operations) and I should consider another measure, maybe the right one is to focus in the min and max operations taken by the best/worst case for a single element and continue from here?

What is the best way to do this?

Jesus

Jesus Salas
  • 149

2 Answers2

2

Since time complexity is dealing with the worst case, your asymptotic upper bound should be above whichever input is causing the highest number of computations to take place. As long as the algorithm is always bound by this behavior, then the time complexity expression is valid.

Essentially, just assume everything is the "worst case" and determine the time complexity of the algorithm from there.

foobar1209
  • 1,047
  • It sounds logical to find the worst case and set the time complexity in this point, however, there is some way to express the best/middle/worst case? – Jesus Salas Mar 19 '14 at 04:22
  • @JesusSalas Without knowing more about the intricacies of the algorithm, I can't really say. But for best case just assume the "best case" happens for all possible events. However, if you're still looking to represent the time complexity in Big-$O$ notation, you should only be concerned with the worst case since this is an asymptotic upper bound for the entire algorithm, regardless of how "well things turn out" when it's running. – foobar1209 Mar 19 '14 at 04:28
  • you are right, I'll stick to worst case measuring maximum number of operations required to process a given set. In fact in the algorithm there is a maximum space that can be filled (let's say number of buckets) and when these buckets are 100% filled the algorithm just halt, so might be right to express the time complexity as 'the number of operations required to fill all the available buckets for a given set'. What do you think? – Jesus Salas Mar 19 '14 at 04:46
  • @JesusSalas If that's what takes the most computations, then that's the way to go. – foobar1209 Mar 19 '14 at 04:57
  • thinking about the algorithm and what it does is "to fill the buckets until there are no more left" so seems the best approach, thank you for helping me to figure out this :) – Jesus Salas Mar 19 '14 at 05:01
  • @JesusSalas You are very welcome. :) – foobar1209 Mar 19 '14 at 05:08
0

Time complexity is (usually) the worst-case time complexity, an upper bound, if no other measure is specified. Alternatives include "average time" complexity (which really only makes sense if the set of inputs has a known probability distribution) and even "best time" complexity, which is a lower bound.

In the simplest case, can you find a simple expression that depends on the details of the algorithm that bounds the runtime? For example, "the product of the length of the list and the largest coefficient in the list" (assuming list elements have "coefficients" or can be coerced into numerical representation of difficulty)? Then the right thing to do is express this relationship: "$O(n M)$, where $n$ is the length of the list and $M$ is the largest coefficient in the list." This is somewhat finer grained than just taking the worst possible outcome when you know more due to algorithm analysis.

Sometimes one has a two-stage algorithm (for a simple example, there are obvious extensions) with a parameter where one stage is faster or slower and the other is slower or faster, respectively, depending on the parameter. (The Number Field Sieve is such an algorithm, with respect to the size of the factor base providing a tradeoff in sieving time or relation finding time.) There is clearly a trade-off between speed in the one stage and speed in the other. While it might be wonderful to know what this trade-off is and use it to select the best value of the parameter, frequently the best one can do is sum the worst case in each stage and observe that the result in practice will frequently be much better.

Eric Towers
  • 67,037