1
$\begingroup$

if 0==(n mod 4) then do somthing ϴ(n^2)

else if 1==(n mod 4) then do somthing ϴ(n^3)

else if 2==(n mod 4) then do somthing ϴ(n^4)

else if 3==(n mod 4) then do somthing ϴ(n^5)

what is best case and worst case for this algorithm?

$\endgroup$
1
$\begingroup$

Best case and worst case are about the complexity for a fixed input length. As an example, suppose we are sorting an array of length $n$. There are many possible arrays of length $n$. On some of them the algorithm will be faster, on some it will be slower.

In your case, in contrast, the running time doesn't depend on the input, but only on its length. Therefore the best case and the worst case are both $$ \begin{cases} \Theta(n^2) & \text{if } n \equiv 0 \pmod{4}, \\ \Theta(n^3) & \text{if } n \equiv 1 \pmod{4}, \\ \Theta(n^4) & \text{if } n \equiv 2 \pmod{4}, \\ \Theta(n^5) & \text{if } n \equiv 3 \pmod{4}. \end{cases} $$

$\endgroup$
  • $\begingroup$ I don't think I get it. In my opinion, I think the best case is just Θ(n^2) (when the input hits the first branch and the worst case is Θ(n^5) when the input hits the last branch. Can you explain why my answer is wrong? $\endgroup$ – Brian Apr 8 '18 at 14:02
  • $\begingroup$ Perhaps our definitions of best case and worst case are different. What is your definition? $\endgroup$ – Yuval Filmus Apr 8 '18 at 14:05

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.