Am I allowed to simplify terms while calculating Big O?

Question

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.

Answer 1

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).