[Solved]: Big O and program calls with varied input sizes

Problem Detail: 

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?

Asked By : user1171618

Answered By : Gilles

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14532

3.2K people like this

 Download Related Notes/Documents