Time complexity of arithmetic operations

Question

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
    }
}

Answer 1

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).

In most elementary algorithms, large integers do not show up, so you can just assume that arithmetic operations on variables take constant time. This is intended to be the case in all your examples.