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

Thanks in advance

Asked By : mrjasmin

Answered By : p.j

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14298

3.2K people like this

 Download Related Notes/Documents