# Am I allowed to simplify terms while calculating Big O?

I want to calculate the runtime of the following function

T(n) = (1+2+3+4+5+...+n)/n

At first this doesnt seemed hard to me because it can be solved easily by transforming the formula

T(n) = (n(n-1)/2)/n = (n^2-n)/n = n-1 which leads into O(n).

By thinking about this function i struggled. I am not sure if I am allowed to curtail n, because I dont know the code behind that function.

For example it could be something like

``````method foo()
{
methodWhichTakesNCubeAmountOfTime(); //Build sum, O(n^2)
methodWhichTakesNAmountOfTimeAndCantBeSimplified(); //O(n)
}
``````

For this method I would get n cubes as runtime.

O(n^2) + O(n) = O(n^2)

I know that these method doesnt cover the original term but i hope you get what i meant: The divided by n could be a completly differnt function (which has accidently a complexity of n) and therefore i cannot curtail the other n's with it.

So i am confused. Am i allowed to transform terms normally during calculation the Big O or do some math rules dont apply here?

Thanks.

• Am I understanding correctly that you have a function that, for a given `n`, computes `T(n) = (1+2+3+4+5+...+n)/n`. And you want to know the runtime of that function? Jan 20, 2018 at 14:24

Not only can you, it is in very definition of O-complexity.

The O-complexity is not really as simple as most laymen programmers understand it.

Simply said, the O is defined asymptotically. That means, that you are trying to understand how the algorithm would behave if n was approaching infinity. And in majority of cases, one term dominates the calculation. Your example of

``````O(n^2) + O(n) = O(n^2)
``````

is good representation of that. While for small `n`, the `O(n)` does influence the time, for `n` approaching infinity, `O(n)` becomes negligible compared to `O(n^2)`. So it is fine to just ignore it.

This is also why you see Big-O often with only single term. Because if this term is in complexity equation, it would dominate it as `n` approaches infinity.

Also one note. While Big-O is good way to gauge performance of an algorithm, it is more of a theoretical mathematical tool, than practical way to asses algorithms.

For example, you could have two algorithms. One `O(n^2)` and second `O(1000*n)`. The first one would clearly be faster for `n` smaller than 1000. But because the constants are dropped for complexity to be "correct" then second would have to be really written as `O(n)`.

• Your last paragraph is a good explanation why many sort functions use insertion sort for a small number of values (say, 1000), but switch to an algorithm with a better big O for sets larger than that. Jan 20, 2018 at 17:54