complexity of given code?

Question

I am trying to find out the complexity of the given code below as a function of the problem size n.

sum = 0;

if (EVEN(n))
    for (i = 0; i < n; i++)
      if (i%2 == 0)
        O(logn)
      else
        sum ++;
else
    sum = sum + n;

Here is my answer but I am not sure if I did it correct.

sum=0; is equal to O(1).

The first if else loop consists of a nested for loop, with a nested if statement. So it would be n times the code inside the for loop. Since its if statement and will be either block 1 or block 2. Since O(logn) is slower than sum ++ which is O(1) it is O(logn). So it is O(n)*O(logn).

Hence the final answer would be O(1) + n*O(logn). Is this correct??

I was wondering about the best case and average case. Here is my explanation, does this sound correct? Now let’s consider the best case, where n is not even. Since n is not even the code inside the first if statement will not execute. So we need to look at the code sum = sum +n. This is running time of O(1). Adding it up it would be O(1) + O(1) = 2*O(1), which is equal to O(1). So the best case would be O(1). The average is O(n*log(n))+ O(1) / 2 — Steve S
– Steve S, Commented Oct 11, 2012 at 3:24

Ivan Koblik · Accepted Answer · 2012-10-09 18:31:04Z

2

Yeap seems to be correct if you're talking about worst running time. You can rewrite O(n)*O(logn) as O(n*log(n)).

answered Oct 9, 2012 at 18:31

Ivan Koblik

4,3351 gold badge32 silver badges33 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

FSP · Accepted Answer · 2012-10-09 18:38:05Z

0

Yes, O(nlog(n)) would be the complexity.

answered Oct 9, 2012 at 18:38

FSP

4,8572 gold badges21 silver badges19 bronze badges

1 Comment

Steve S Over a year ago

I was wondering about the best case and average case. Here is my explanation, does this sound correct? Now let’s consider the best case, where n is not even. Since n is not even the code inside the first if statement will not execute. So we need to look at the code sum = sum +n. This is running time of O(1). Adding it up it would be O(1) + O(1) = 2*O(1), which is equal to O(1). So the best case would be O(1). The average is O(n*log(n))+ O(1) / 2

Collectives™ on Stack Overflow

complexity of given code?

2 Answers 2

Comments

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Related