2
$\begingroup$

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
    }
}
$\endgroup$
  • 1
    $\begingroup$ We typically do not answer "check my answer" questions here, unless you have any specific worries. $\endgroup$ – Yuval Filmus Dec 30 '17 at 10:28
  • $\begingroup$ 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.... $\endgroup$ – Michael Dec 30 '17 at 10:33
  • $\begingroup$ As Yuval Filmus mentioned, I've added a question that makes me confuse . $\endgroup$ – Michael Dec 30 '17 at 13:48
  • $\begingroup$ I think our reference question may be a duplicate. $\endgroup$ – Raphael Dec 31 '17 at 9:33
4
$\begingroup$

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.

$\endgroup$

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.