Analyze Code

Determine \Theta for the following code fragment in the average case. Assume that all variables are of type "int".

              sum = 0;
              if (EVEN(n))
                for (i = 0; i < n; i++)
                  sum++;
              else
                sum = sum + n;

\Theta(n)

\Theta(\log n)
\Theta(n^2 \log n)
\Theta(1)
\Theta(n^2)
\Theta(n \log n)
\Theta(n^3)
\Theta(2^n)

How much work is done by each branch of the if-then-else statement? Use the more expensive one.