1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Raphael Dec 1 '18 at 11:09
  • $\begingroup$ 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! $\endgroup$ – Raphael Dec 1 '18 at 11:09
  • $\begingroup$ 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 ?? $\endgroup$ – NANA Dec 1 '18 at 13:07
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ "we will have $n^2$" -- not so. The loop doesn't start withi=1. $\endgroup$ – Raphael Dec 1 '18 at 11:10
  • $\begingroup$ 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 ? $\endgroup$ – NANA Dec 1 '18 at 13:09
  • 1
    $\begingroup$ @NANA Nope. I mean $t_a(n)=\sum_{j=4}^{n^{2}}1= n^{2} - 3$. $\endgroup$ – OmG Dec 1 '18 at 13:15
  • 1
    $\begingroup$ @NANA I'd say that's a better starting place, yes, as it follows a general rule. Manipulate the sum until you can simplify it $\endgroup$ – Raphael Dec 1 '18 at 13:27
  • $\begingroup$ 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 $\endgroup$ – NANA Dec 1 '18 at 14:47

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.