# Running time with while loop

What's the running time of:

foo(n)
if(n==1) return;
int i=1;
while(i<n)
{
i=i+2
}
foo(n-2)


There are $n/2$ recursive calls to foo but how to add to the calculation the while loop

## 2 Answers

You can write the relation likes the following: $$T(n) = T(n-2) + \frac{n}{2}$$ $$T(n) = \frac{n}{2} + \frac{n-2}{2} + \frac{n-4}{2}+\cdots +\frac{n-(n-2)}{2} =$$ $$\frac{n^2-2(1+2+3+\cdots+(\frac{n}{2}-1))}{2}=$$ $$\frac{n^2-(\frac{n}{2}-1)\times \frac{n}{2}}{2}= \Theta(n^2)$$

The number of the iterations of the while loop is

$$n/2+(n-2)/2 + (n-4)/2 + \dots +1$$

which is $O(n^2)$.

• What about the $n/2$ calls? so what's the total time? – Error 404 Jan 20 '18 at 18:10
• We prefer detailed answers that come with explanation. Where did that expression come from? What's the rationale/justification for it? What approach did you use to get that answer? – D.W. Jan 21 '18 at 1:53