# Find the efficiency class

I have to find the efficiency class of this algorithm

b = 3
a = 4
for i = 4 to n^2
if (i mod 2 == 0)
a = a+2
else
b = b*3
end for


I solve it like this, first I find the time for executed a then b and the total is the addition, is it right? I'm not sure if I have to do it like this or not, I let $$n=\frac{n^2}{2}$$ because of the $$\bmod 2$$ is it right?

$$t_a(n)=\sum_{j=1}^{n^{2}/2}1=\dfrac{n^{2}}{2}$$

$$t_b(n)=\sum_{j=4}^{n^{2}}1-\dfrac{n^{2}}{2}=n^{2}-\dfrac{n^{2}}{3}-3$$

$$t(n)=\dfrac{n^{2}}{2}+n^{2}-\dfrac{n^{2}}{3}-3=\Theta (n^{2})$$ by the polynomial theorem.

• 0) Your basic approach looks good. 1) Check the limits of your sums, though. Since there are as many odd as even numbers, $t_a$ and $t_b$ should be very similar! 2) You didn't count everything: evaluating the if and for statements as well as the initialisation have costs, too. Even if you're only counting arithmetic operations, not that maintaining i takes such operations! – Raphael Dec 1 '18 at 11:09
• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – Raphael Dec 1 '18 at 11:09
• Yes! for the limits I saw it similar to odd and even number but didn't know how to write it as n, for even the 2k you mean I can write it as 2n^2 ?? – NANA Dec 1 '18 at 13:07

The final result is true. But, you have a fault in your computation, as in each iteration you have at least a comparison. Hence, instead of $$\frac{n^2}{2}$$, we will have $$n^2 - 3$$. Anyhow, the final result is the time complexity is $$\Theta(n^2)$$.
• "we will have $n^2$" -- not so. The loop doesn't start withi=1. – Raphael Dec 1 '18 at 11:10
• you mean I must start solving it from $=\sum_{i=4,6,8,..n^{2}}^{n^{2}}1$ ? then I give j=1 so I can start from 1 ? just like what I do before ? – NANA Dec 1 '18 at 13:09
• @NANA Nope. I mean $t_a(n)=\sum_{j=4}^{n^{2}}1= n^{2} - 3$. – OmG Dec 1 '18 at 13:15
• why only $n^{2}-3$? I have to subtract the time of $a$ also right that's why it is $n^{2}-3-n^{2}/2$ @OmG – NANA Dec 1 '18 at 14:47