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.

Inertial Ignorance
  • 545
  • 6
  • 14
  • 2
    Possible duplicate of [What is O(...) and how do I calculate it?](https://softwareengineering.stackexchange.com/questions/132331/what-is-o-and-how-do-i-calculate-it) – gnat Apr 22 '18 at 20:41

1 Answers1

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.

Inertial Ignorance
  • 545
  • 6
  • 14