Question

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.

Was it helpful?

Solution

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.

Licensed under: CC-BY-SA with attribution
scroll top