0
$\begingroup$

How many operations are performed in the following in order to get a running time function of an algorithm:

  1. x = x + 1

  2. x += 1

  3. x++

I know that in (1) there are 2 operations: an assignment and an addition.

Does the same criteria apply to (2) and (3)?

$\endgroup$
2
  • 6
    $\begingroup$ I believe the answer may greatly depend on the compiler and the specific implementation (e.g., is $x$ kept in a register or in the memory?). A good (optimized) compiler may implement the above three in the same manner, as a single INC operation of a register, or may give totally different implementations (especially if $x$ is a variable of more complicated type) $\endgroup$ – Ran G. Jul 15 '15 at 1:49
  • $\begingroup$ In addition to what @RanG. says, the target architecture is relevant as well. $\endgroup$ – Raphael Jul 15 '15 at 5:37
3
$\begingroup$

Depends. For the purpose of formal analysis, this is usually below our threshold of modelling. Just make a reasonable assumption, or forbid syntactic sugar in your model syntax.

Note that, if you are analysing at this level of detail, working with higher-level languages can be painful. If you want to follow Donald Knuth's lead,

  1. fix a (manageable) machine model and
  2. fix a low-level machine language.

The express your algorithms and this language and analyse. They may not look as nice as high-level pseudocode versions, but analysis is unambiguous.

$\endgroup$
0
$\begingroup$

All of these statements are equivalent, and take $O(1)$ time (I'm assuming x has basic type like integer or floating point). Their actual "physical" running time depends on many factors. For example, whether $x$ is stored in memory, on the stack, or in a register. Pipelining issues can also be relevant, and it is hard to predict the actual running time of any particular statement; in particular, the running times of other statements could be affected due to pipelining issues or even caching issues. Asymptotic analysis avoids these issues by simply stating the running time as $O(1)$.

Naturally, there are problems with asymptotic analysis: it ignores constants! There are at least two ways of dealing with that. One is to count something very specific, like comparisons in a sorting algorithm. The other is to forget about asymptotic analysis and just run simulations, empirically determining the running time (though this also suffers from similar issues, for example it could depend on what other processes are currently running on the system).

$\endgroup$
1
  • 1
    $\begingroup$ The third way is to actually assign meaningful constant costs to every statement, and perform a rigorous analysis. Hence this question is (maybe) aiming towards that, I don't see how this answers it. "Just use $O(1)$ or don't do analysis" certainly can not be the answer. $\endgroup$ – Raphael Jul 15 '15 at 5:38

Not the answer you're looking for? Browse other questions tagged or ask your own question.