# Time Complexity of Algorithm

I need help with finding out the time complexity of the following algorithm:

procedure VeryOdd(integer n):
for i from 1 to n do
if i is odd then
for j from i to n do
x = x + 1
for j from 1 to i do
y = y + 1


This is my attempt:

$$Loop1 = \Theta(n)$$ $$Loop2 = \Theta(n)$$ $$Loop2 = O(n)$$

And we also know that loop2 and loop3 will get executed every second time of the execution of the outer loop. So we know that:

$$T(n) = \Theta(n) * 1/2(\Theta(n) + O(n)) = \Theta(n^2)$$

Now to the thing I'm not so sure about, nameley, is Loop3 really $$O(N)$$ and if yes, then is $$\Theta(n) + O(n) = \Theta(n)$$

• Note that loops 2 does something $n+1-i$ times and loop 3 does something $i$ times, so you can just take them as a single loop, repeated $n+1$ times. – Karolis Juodelė Sep 14 '13 at 5:26
$$Loop 1 = \theta(n)$$ Since both loop in total will run n times so, $$Loop 2 + Loop3 = \theta(n)$$ $$T(n) = \theta(n) * 1/2 ( \theta(n)) = \theta(n^2)$$