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!

  • $\begingroup$ Have you read, e.g., cs.stackexchange.com/a/23594/2213 and cs.stackexchange.com/a/197/2213 ? $\endgroup$ – Marcus Ritt Jun 4 '19 at 22:55
  • $\begingroup$ Possible duplicate of How to come up with the runtime of algorithms? $\endgroup$ – dkaeae Jun 5 '19 at 7:07
  • $\begingroup$ @dkaeae I don't care about the answers in that question. The flag "mark as a duplicate" is used to mark duplicate questions not answers! I think you should distinguish that. Anyway, you're not the only one that does this on SE communities, unfortunately. $\endgroup$ – nbro Jun 5 '19 at 16:38
  • $\begingroup$ @nbro Duplicate does not mean it's the same question. It means the question already has an answer to it (namely in the question it duplicates). This is standard on SE. Note not all duplicate questions get deleted. $\endgroup$ – dkaeae Jun 5 '19 at 16:42
  • $\begingroup$ @dkaeae "Duplicate does not mean it's the same question.", who told you this is standard? Furthermore, the answer to that other question are not the same as the answers to this question, so it seems you are wrong. $\endgroup$ – nbro Jun 5 '19 at 16:44

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.

  • $\begingroup$ In other words: you choose what the elementary operations should be in your model. $\endgroup$ – Jörg W Mittag Jun 6 '19 at 18:50

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.