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

Thanks in advance

• 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
• Please take care in the future to use text instead of image files. Also, similar things have been covered multiple times (see e.g. here or, more generally, runtime-analysis). – Raphael Sep 16 '13 at 7:44

## 1 Answer

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

• Thank you. Just one more question, is it also true that loops 2 and 3 belongs to O(n) and also Omega(n) ? Thanks – mrjasmin Sep 14 '13 at 9:51
• You can write but then it will not be a tight analysis and some people may not like this because it is clear that in total 2nd and 3rd loop will run n-times no more and no less ,then theta(n) is correct.. – p.j Sep 14 '13 at 12:04
• But the second and 3rd loop will right n+1 times ? – mrjasmin Sep 14 '13 at 12:34
• Yes I wrote it n my mistake, but still it will be theta(n) .. – p.j Sep 14 '13 at 12:36