2
$\begingroup$

Suppose I have a program p that has time complexity $O(n)$ and a second program q that calls program p $m$ times. If we know the input size of p will be the same every one of those times (n), we can say that the complexity of q is $O(m \times n)$. This case sounds pretty simple to me.

However, suppose the input size of p varies over these $m$ times, from $0$ to $m-1$.

If we knew that p ran precisely $f(n) = a \times n$ instructions for an input of size $n$, it would be simple: q would run $a \times 0 + a \times 1 + \ldots + a \times (m-1) = am(m-1)/2$ instructions exactly, which is $O(m^2)$.

However, in this case, all we know is that $f(n)$ is below $a \times n$ for all $n$ greater than some $n_0$, by the definition of big-O. We can't say for sure that $f(0) + f(1) + ... + f(m-1)$ is below $a \times 0 + a \times 1 + \ldots + a \times (m-1)$, because we don't know that $0, 1, \ldots, m-1$ are greater than this $n_0$. For this reason, I don't think we can say that q runs in $O(m^2)$.

Is there a way, in this case, when all we know is the big-O behaviour of p, to analyze q?

What if we replace all the big-O's with big-Theta's?

$\endgroup$
  • 2
    $\begingroup$ You can in fact say that such a constant exists for all $n < n_0$: just take $\max_{1 \leq i \leq n_0} \{f(i)\}$; whenever you know that for almost all $n$ some bound holds, then you can just take the maximum/minimum over all the finitely many $n$ where it doesn't hold and scale it appropriately for those. $\endgroup$ – G. Bach Sep 23 '13 at 0:17
1
$\begingroup$

Actually, since you did not specify what q does beyond calling p, there is too little information to know anything about the time complexity of q, except that it is $\Omega(m)$ since it must execute at least $m$ calls to p, whatever else it does.

Let's look at a special case which is probably what you were thinking of. Suppose that q looks like this:

data := preprocess(input);
for i = 0 to m -1 do
    data := p(data);
end

That is, p potentially has access to all the internal data of q. This is the most general case. Where this program is not general is that in the loop, it does nothing but call p.

The running time of this program is $Q = A + \left( \sum_{i=0}^{m-1} P(S_i) \right) + O(m)$ where

  • $A$ is the time taken to run the preprocessing step;
  • $P(s)$ is the maximum time taken by p to process data of size $s$;
  • $S_i$ is the size of data when the $i$th step starts.

The assumption on the running time of p is that $P(s) = O(s)$. That is, there exists $n_0$ and $a$ such that if $s \ge n_0$ then $P(s) \le a \, s$. This gives us a bound for the running time when $s$ is large. When $s$ is small, we can simply use the maximum running time of p for small sizes: there are only a finite number of sizes that are smaller than $n_0$. Let $\hat P = \max\{P(0), P(1), \ldots, P(n_0-1)\}$.

Then, expanding the definition of $O(m)$ in the equation for $Q$ above, we get that there exist $m_0$ and $b$ such that for $m \ge m_0$, $$ \begin{align} Q &\le A + \left( \sum_{i=0}^{m-1} P(S_i) \right) + b m \le A + \left( \sum_{i=0}^{m-1} \max \{\hat P, a\, S_i\} \right) + b m \\ &\le A + \left( \sum_{i=0}^{m-1} (\hat P + a\, S_i) \right) + b m \le A + a \left( \sum_{i=0}^{m-1} S_i \right) + (b + \hat P) m \\ &\le A + a \left( \max\nolimits_{i=0}^{m-1} S_i \right) m + (b + \hat P) m \end{align} $$

Notice how the constant $\hat P$ resulting from the small cases of running the subprogram has been absorbed into the multiplicative constant for the calling program. This is a general phenomenon: when studying the complexity of algorithms, the performance of subtasks on small inputs is irrelevant for obtaining a first bound on the complexity of the whole task. It can be relevant to prove better bounds (sometimes, the inequalities above are too crude).

We aren't quite there yet: the component $\max\nolimits_{i=0}^{m-1} S_i$ remains unevaluated. The behavior of this component depends on what p does. For example, if p is a program that duplicates its input, say

return arg ++ arg

where ++ is the string concatenation operator and string concatenation takes $\Theta(n)$ where $n$ is the length of the string, then $S_i = S_0 2^i$ and all the analysis above tells us is that $Q$ grows exponentially with $m$ — which is the case.

If we additionally assume that p does not change the size of the data and that the preprocessing step is linear in the size of the input, then $S_i$ does not depend on $i$ and is $O(n)$ (i.e. $S_i \le S n$ for large enough $n$), and we have (for sufficiently large $n$ and $m$): $$ Q \le a' n + S n m + (b + \hat P) m $$ For sufficiently large $n$ and $m$, the dominant term is $S n m$: the time complexity of Q is $O(m n)$.

Note again that the reason why it took a lot of additional assumptions to prove that Q runs in $O(m n)$ is not the running time of p on smaller inputs, it's because for all we knew p could receive some very large inputs.

$\endgroup$
  • $\begingroup$ "If we know the input size of p will be the same every one of those times (n)" - does this not cover everything we need to know about the input of p? $\endgroup$ – G. Bach Sep 23 '13 at 0:31
  • $\begingroup$ @G.Bach The question is about “However, suppose the input size of p varies over these m times”. And “0 to m-1” is underspecified, since it doesn't give the scale. $\endgroup$ – Gilles Sep 23 '13 at 0:33
  • $\begingroup$ Ah, of course I had forgotten that part and failed to read it again. I don't understand how the bound of $m$ is underspecified. $\endgroup$ – G. Bach Sep 23 '13 at 0:34
  • $\begingroup$ @G.Bach Ah, that one is my mistake, I overcomplicated this a little. $\endgroup$ – Gilles Sep 23 '13 at 0:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.