Cheap and Secure Web Hosting Provider : See Now

# [Solved]: Time Complexity of Algorithm

, ,
Problem Detail:

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

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