Вопрос

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.

Это было полезно?

Решение

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.

Лицензировано под: CC-BY-SA с атрибуция
scroll top