Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote -1 down vote favorite

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

share|improve this question
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 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 at 7:44

1 Answer

up vote 1 down vote accepted

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

share|improve this answer
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 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.. – Parag Jain Sep 14 at 12:04
But the second and 3rd loop will right n+1 times ? – mrjasmin Sep 14 at 12:34
Yes I wrote it n my mistake, but still it will be theta(n) .. – Parag Jain Sep 14 at 12:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.