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

  • $\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$ – Karolis Juodelė Sep 14 '13 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 '13 at 7:44

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

| cite | improve this answer | |
  • $\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 '13 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$ – p.j Sep 14 '13 at 12:04
  • $\begingroup$ But the second and 3rd loop will right n+1 times ? $\endgroup$ – mrjasmin Sep 14 '13 at 12:34
  • $\begingroup$ Yes I wrote it n my mistake, but still it will be theta(n) .. $\endgroup$ – p.j Sep 14 '13 at 12:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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