# Time complexity of arithmetic operations

I want to calculate the time complexity of the listed algorithms, please correct if I'm doing something wrong: The question is, do some operations like multiplying, dividing, or plus really affect on time complexity ?

// Time complexity is O(log n)
void calculate(n: Int) {

while (k < n) {
k *= 2 //or k *= k
}
}

// Time complexity is O(n)
void calculate(n: Int) {

while (k < n) {
k += 1000
}
}

//Time complexity is O(log n)
void calculate(n: Int) {

k = n

while (k > 1) {
k /= 4
}
}

• We typically do not answer "check my answer" questions here, unless you have any specific worries. Dec 30, 2017 at 10:28
• Oops, I am sorry, it's my first exp using such platforms. I tried to search something similar but I don't really found anything.... Dec 30, 2017 at 10:33
• As Yuval Filmus mentioned, I've added a question that makes me confuse . Dec 30, 2017 at 13:48
• I think our reference question may be a duplicate.
– Raphael
Dec 31, 2017 at 9:33

Your question is excellent! Unfortunately, my answer might disappoint you: the complexity of arithmetic operations depends on the computation model; to some extent, it's up to you to decide how much does it cost to add or multiply two numbers. Usually when analyzing algorithms, we assume the unit cost RAM model, in which arithmetic operations on two "reasonably sized" integers takes time $O(1)$. Here "reasonably sized" means of length $A\log n$, or equivalently, of absolute value at most $n^A$ (here $n$ is the size of the input). The constant $A>0$ should be fixed per algorithm. Its exact value doesn't matter, since we can simulate arithmetic operations on operands of size $m^2$ using $O(1)$ arithmetic operations on operands of size $m$.
In some cases, we have to do arithmetic on large integers. This happens in cryptography, for example. When adding or multiplying large numbers, operations no longer take $O(1)$ even in the unit cost RAM. For example, adding $m$-bit integers takes time $\Theta(m)$, and the best known algorithm for multiplication runs in $\tilde{O}(m\log m)$ (the tilde hides smaller multiplicative factors).