Search code examples
algorithmcomplexity-theory

complexity of (n^2/2)+(n^2*logn)


I'm trying to solve exercises about algorithms complexity and in a case like the one in the title I'm not sure on how to proceed.

I know that I would have to find the fastest growing term and remove the coefficient unless the coefficient includes another term:

for example: (n^2)*logn complexity is O((n^2)*logn) and (n^2)*2 complexity is O(n^2).

What I did was simplifying the function to n^2(1/2+logn), but after that I'm not sure if the complexity would just be O(n^2(1/2+logn)) or if the result is something else.


Solution

  • Like Damien suggested in the comment, the answer is: O(1/2 + logn) = O(logn)