0

Before this gets accused of being a duplicate, I have looked everywhere on StackOverflow for this answer and have not been able to find something that can explain this to me, so please read the entirety first.

Suppose you need to write a function that takes an integer n and returns the sum of the positive integers from 1..n (I will use C).

int sum_of_integers(int n) {
    int i, counter = 0;
    for(i = 1; i <= n; i++)
        counter += i;
    return counter;
}

Obviously, this algorithm is in O(n) time, since the number of instructions it runs is proportional to the input size n.

However, consider this implementation, using the mathematical truth that 1+...+n = (n)(n+1)/2.

int sum_of_integers(int n) {
    //Trying to avoid potential int overflow
    //And take into account int division
    if(n % 2 == 0)
        return (n/2)*(n+1);
    return ((n+1)/2)*n;
}

My Question: Since multiplication is technically in big-O > O(n), is the first implementation preferred? Is the second implementation considered to be in O(1) or not?

To me, because it does not matter what the size of n is for the second implementation since the same operations are being performed the same amount of times, I feel like it should be in O(1). On the other hand, the second implementation may actually be running more instructions based on the implementation of the multiplication operator.

adamsuskin
  • 547
  • 3
  • 16
  • Can you explain further? Why does it not matter that the operation of multiplication is not in O(1)? – adamsuskin Oct 07 '15 at 22:14
  • why do you even add that condition in the second examplecode? `(n + 1) * n` is always divisible by 2 –  Oct 07 '15 at 22:15
  • Multiplication is O(d) where d is the size of the multiplicands, but the number of data items n can easily be very much larger than d, so second option is preferred. Also, multiplication is often done with hardware, so the coefficient of O(d) is very small... – antlersoft Oct 07 '15 at 22:15
  • @Paul Because `(n+1) * n` could hypothetically cause integer overflow, so it is better to divide by the 2 first. But in order to avoid a possible truncation due to integer division, I check for which term, `n` or `n+1` is the term divisible by 2. – adamsuskin Oct 07 '15 at 22:16
  • 1
    Check this thread http://stackoverflow.com/questions/21819682/is-integer-multiplication-really-same-speed-as-addition-on-modern-cpu even though multiplication may be claimed to take longer, you are doing more additions in first case. The second case is log-logarithmically faster, and therefore O(1). – ergonaut Oct 07 '15 at 22:20
  • 1
    Give it a try. Take n=1000000000 and try the first and the second option. Which one was faster? (Ignore the overflow, concentrate on the run time) – Alex Lop. Oct 07 '15 at 22:20

1 Answers1

3

Schoolbook multiplication takes time O(b^2) where b is the number of bits in the numbers, so using the formula n(n+1)/2 takes time O((log n)^2) which is much faster than O(n).

Charles
  • 11,269
  • 13
  • 67
  • 105
  • 1
    That's only true for arbitrary-precision arithmetic. Computers normally use fixed precision, so multiplication is O(1). – Barmar Oct 07 '15 at 22:19
  • 2
    The value in this answer is that it clears up a misconception in the OP. The OP makes the patently false claim that *"multiplication is technically in big-O > O(n)"*. In fact, as stated in this answer, multiplication *"takes time O((log n)^2)"*. The other misconception in the OP is that big-O even applies. Big-O analyzes asymptotic behavior for very large values of `n`. It doesn't really apply in a case where the multiplication is done (in highly parallelized hardware) as a single processor instruction. – user3386109 Oct 07 '15 at 22:45
  • Thank you, this was the most helpful! If I am curious why it does not apply @user3386109, is there anywhere to find more information? – adamsuskin Oct 07 '15 at 22:46
  • Understanding when big-O applies is something that has to be learned over time. The biggest problem is that the concept of big-O is loosely defined as applying to "large" values of `n`, leaving room for debate as to the definition of "large". In the case of multiplication, a large value of `n` needs to exceed the largest value that the processor can handle with a single instruction. Otherwise, the parallel hardware in the processor makes multiplication seem like an O(1) operation, when in fact the processor is doing a lot of work to create that illusion. – user3386109 Oct 07 '15 at 22:54