2

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.

1
  • 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

1 Answer 1

7

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

1
  • 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.