-1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Sep 14, 2013 at 5:26
  • $\begingroup$ 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). $\endgroup$
    – Raphael
    Sep 16, 2013 at 7:44

1 Answer 1

1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Thank you. Just one more question, is it also true that loops 2 and 3 belongs to O(n) and also Omega(n) ? Thanks $\endgroup$
    – mrjasmin
    Sep 14, 2013 at 9:51
  • $\begingroup$ 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.. $\endgroup$
    – Parag
    Sep 14, 2013 at 12:04
  • $\begingroup$ But the second and 3rd loop will right n+1 times ? $\endgroup$
    – mrjasmin
    Sep 14, 2013 at 12:34
  • $\begingroup$ Yes I wrote it n my mistake, but still it will be theta(n) .. $\endgroup$
    – Parag
    Sep 14, 2013 at 12:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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