# How to compute time complexity of a program if the time complexity of a function called inside a loop is known? [duplicate]

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?

## 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.

• 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. – D.W. Jan 23 '15 at 17:13
• No, if $f$ is exponential then so will the given program be. – Tom van der Zanden Jan 23 '15 at 18:01
• @TomvanderZanden, then why was $\theta(m)$ neglected? – Siddharth Thevaril Jan 23 '15 at 18:31
• The explanation is misleading. I doubt the person who wrote it actually understood the situation. – Yuval Filmus Jan 23 '15 at 18:41

## 1 Answer

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)$.