# 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

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