Algorithm Big O – Growth Rate of (n^2 + n) / 2

algorithmsbig o

I'm asking this question because I am confused about one aspect regarding big O notation.

I am using the book, Data Structures and Abstractions with Java by Frank Carrano. In the chapter on the "Efficiency of Algorithms" he shows the following algorithm:

int sum = 0, i = 1, j = 1
for (i = 1 to n) {
    for (j = 1 to i)
        sum = sum + 1
}

He initially describes this algorithm as having a growth rate of (n2 + n)/2. Which looking at it seems intuitive.

However, it is then stated that (n2 + n)/2 behaves like n2 when n is large. In the same paragraph he states (n2 + n)/2 also behaves much like n2/2. He uses this to classify the above algorithm as O(n2).

I get that (n2 + n)/2 is similar to n2/2 because percentage wise, n makes little difference. What I do not get is why (n2 + n)/2 and n2 are similar, when n is large.

For example, if n = 1,000,000:

(n^2 + n) / 2 =  500000500000 (5.000005e+11)
(n^2) / 2     =  500000000000 (5e+11)
(n^2)         = 1000000000000 (1e+12)

That last one is not similar at all. In fact, quite obviously, it's twice as much as the middle one. So how can Frank Carrano say they are similar? Also, how is the algorithm classified as O(n2). Looking at that inner loop I would say it was n2 + n/2

Best Answer

When calculating the Big-O complexity of an algorithm, the thing being shown is the factor that gives the largest contribution to the increase in execution time if the number of elements that you run the algorithm over increases.

If you have an algorithm with a complexity of (n^2 + n)/2 and you double the number of elements, then the constant 2 does not affect the increase in the execution time, the term n causes a doubling in the execution time and the term n^2 causes a four-fold increase in execution time.
As the n^2 term has the largest contribution, the Big-O complexity is O(n^2).

Related Topic