1
$\begingroup$

This question already has an answer here:

This is the question-

Let $A[1,....,n]$ ba an array storing a bit $(1\,\,or\,\,0)$ at each location, and $f(m)$ is a function whose time complexity is $\theta(m)$. Consider the following program -

counter = 0;
for( i = 1; i <= n; i++)
{
    if(A[i] == 1)
        counter++;
    else
    {
        f(counter);
        counter = 0;
    }
}


Options are :

(A)$\Omega(n^2)$
(B)$\Omega(n\log n)$ and $O(n^2)$
(C)$\Theta(n)$
(D)$\mathcal{O}(n)$

The solution says - "Since it contains only one loop, so compute with linear complexity, hence the complexity will be $\Theta(n)$".

My doubt is, what if the time complexity of the function $f(m)$ was given to be $\theta(2^n)$ or of the order that grows in exponential time? Would the solution given in the book be correct in case of exponential time?

$\endgroup$

marked as duplicate by D.W., Juho, Raphael Jan 24 '15 at 9:28

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ 1. Please try to avoid extraneous information and craft a focused question. I looks like that entire long multiple-choice problem is irrelevant, and you are asking about a different situation -- one that could be explained in a single line. Ask the question in a general form that is easiest for readers to understand and most likely to be useful to others. 2. This is already covered in our reference questions on runtime analysis; I encourage you to study them. $\endgroup$ – D.W. Jan 23 '15 at 17:13
  • $\begingroup$ No, if $f$ is exponential then so will the given program be. $\endgroup$ – Tom van der Zanden Jan 23 '15 at 18:01
  • $\begingroup$ @TomvanderZanden, then why was $\theta(m)$ neglected? $\endgroup$ – Siddharth Thevaril Jan 23 '15 at 18:31
  • $\begingroup$ The explanation is misleading. I doubt the person who wrote it actually understood the situation. $\endgroup$ – Yuval Filmus Jan 23 '15 at 18:41
1
$\begingroup$

This is actually an example of amortized analysis. The easiest way to see what's going on is to separate $A$ as follows: $A=1^{n_1}01^{n_2}0\cdots1^{n_k}$. You can check that the function $f$ is called with arguments $n_1,n_2,\ldots,n_{k-1}$. Since $n_1+\cdots+n_k = n-(k-1)$, in particular $n_1+\cdots+n_{k-1} \leq n$, and so the total time spent running $f$ is $O(n_1+\cdots+n_{k-1}) = O(n)$. The time spent on executing the rest of the program is $\Theta(n)$, and so the total running time is $\Theta(n)$.

If we did want to use amortized analysis, the idea would be as follows. Suppose for simplicity that $f(m)$ runs in time $m$ (exactly). Each time the counter is incremented, we set aside another "time unit", and withdraw the time units set aside when $f$ is called. You can check that we always have enough time units in store. Under this scheme of accounting, incrementing the counter takes time $O(1)$, and calling $f(m)$ takes no time; this can only overestimate the actual running time (since we might have leftover time units). Therefore the total running time is $O(n)$.

$\endgroup$

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