0

Take the following algorithm with two separate sections, and the sections do not influence each other whatsoever (the function is not recursive, as well).

void algorithm(int x)
{
   // This section of the algorithm has linear growth... O(x)

   // This section of the algorithm has x * logarithmic growth... O(xlogx)
}

To determine the algorithm's Big O notation, I did the following:

Algorithm run time approximately = xlogx + x

The greatest term is xlogx, so the algorithm's Big O = O(xlogx).

Is this correct? Or do I need to factor in more information from the two sections of the algorithm. For example, the first section actually performs 10x operations, but in my calculations I only use its O(x) notation.

2

O(x) + O(xlog(x)) = O(xlog(x)) because O(xlog(x)) is the dominant term / superset of O(x).

Algorithms: How do I sum O(n) and O(nlog(n)) together?

See Justin Cave's and davidk01's answers.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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