1
$\begingroup$

i am trying find the Cost of an algorithm. it contains break statements. is there any cost of break and Continue statement in a Algorithm?

$\endgroup$
  • 2
    $\begingroup$ Simply use $\mathcal O(1)$. In some cases it may be 0 as well. $\endgroup$ – Evil Mar 5 '18 at 15:24
  • 3
    $\begingroup$ If you've created multiple accounts, I encourage you to merge them (see cs.stackexchange.com/help/merging-accounts). It's also useful to register your account to make sure you can log back in again. That will let you post comments under your question and edit your question if you need to clarify what you are asking. $\endgroup$ – D.W. Mar 5 '18 at 16:00
3
$\begingroup$

Depends on how close you want to look.

On face value, break, continue, etc. are implemented by unconditional jumps, which are (under most RAM-/CPU-like models) primitive instructions of the machine. So they certainly have some constant cost; $O(1)$ is a valid bound.

That's not very interesting, though: all primitive instructions have constant cost. If you want to answer questions like, "can I speed up my algorithm by adding/removing break/continue?", the situation becomes more involved.

The true cost of jumps depends on many factors, e.g.

  • the type of pipeline the CPU uses,
  • which type of speculative execution happens (if any),

and so on. My guess is that an unconditional jump -- other than conditional jumps -- should behave well in many regards. They are most certainly cheaper than completing the loop would be.

If the true cost matters to you, I recommend you benchmark the alternatives at hand. Be aware that the effect you're trying to measure may be smaller than the noise introduced by benchmarking, and you may have to account for that.

$\endgroup$

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.