3 ms·

I always thought that mathematical operations run in constant time ... how can they not?

• bartonfink 15y ago
  Look at the algorithm you use for adding two integers by hand, for example. You add the ones digits together and possibly have to carry one over. You then add the tens digits and possibly carry over. You repeat as long as the numbers "share" digit places. This isn't constant time because the number of individual digit additions and carries changes based upon the length of the inputs. In fact, this particular algorithm is linear in the number of digits. You could also implement linear addition as a series of increments, as I said above. Translate "a + b" into code looking something like for(int i = 0; i < b; i++){ a += 1; } This obviously runs in linear time, and is how we teach addition at first. It's not an unreasonable thing to assume at first, especially since your professors will almost certainly tell you to assume that, but there can be hidden complexity under the covers. You just don't need to care about it in most cases.