4
$\begingroup$

Wikipedia gives us the following defintion of time complexity:

"In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform."

Now what are these elementary operations ? Are they arithmetic operations or some simpler operations ?
Thanks in advance!

$\endgroup$
4
  • $\begingroup$ Have you read, e.g., cs.stackexchange.com/a/23594/2213 and cs.stackexchange.com/a/197/2213 ? $\endgroup$ Commented Jun 4, 2019 at 22:55
  • $\begingroup$ Possible duplicate of How to come up with the runtime of algorithms? $\endgroup$
    – dkaeae
    Commented Jun 5, 2019 at 7:07
  • $\begingroup$ @dkaeae As far as I'm aware, whether a question is a duplicate of another in principle only depends on the questions themselves and not on their answers. 'Duplicate' means that the set of possible answers of the questions is the same. See e.g. When are two questions considered duplicates?. (the phrasing of dupe questions '... already has an answer' can be confusing here) $\endgroup$
    – Discrete lizard
    Commented Jun 6, 2019 at 8:36
  • $\begingroup$ @dkaeae There is a common exception to this rule, which is closing a specific question as a duplicate of a more general question (such as a reference-question). In this case, only some of the potential answers to the closed question are an answer to the duplicate target. But this kind of duplicate still depends on potential answers, not on actual answers. So, the relevant question is whether explaining the fundamentals of run-time analysis nessecarily explains what should be considered as an elementary operation. I don't think it does, but I can see that others may disagree. $\endgroup$
    – Discrete lizard
    Commented Jun 6, 2019 at 8:36

1 Answer 1

4
$\begingroup$

The set of elementary operations and their cost constitute a model of computation. The most common model of computation used to analyze algorithms is the Random access machine. Briefly, memory is divided into words of size $O(\log n)$ bits, where $n$ is the size of the input to the algorithm. A program consists of a sequence of instructions. The exact set of instructions isn't really set in stone, but usually includes arithmetic instructions (addition, subtraction, multiplication, division with remainder), possibly bitwise instructions, memory dereferencing, control flow, and so on. In the unit cost RAM, the most common model, each instruction operations on a single word, and costs one unit of time.

Other relatively common models of computation include various models of Turing machine, the bit complexity model (in which words consist of a single bit), and logarithmic cost RAM.

$\endgroup$
3
  • $\begingroup$ In other words: you choose what the elementary operations should be in your model. $\endgroup$ Commented Jun 6, 2019 at 18:50
  • $\begingroup$ If my instance is a number $N$, then the size of the instance is $n=log(N)$, am I understanding correctly that my instance is stored in words of size $log(n) = log(log(N))$ in memory? What is the point of that? Why not suppose it is stored in one word of size $n$? $\endgroup$
    – J. Schmidt
    Commented Dec 21, 2022 at 10:24
  • $\begingroup$ The most popular complexity model for operations on numbers is the bit complexity model, though Fürer argued that the word RAM is more realistic even in that case. $\endgroup$ Commented Dec 21, 2022 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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