Is my reasoning to determine this algorithm's Big-O correct?
https://softwareengineering.stackexchange.com/questions/369818
-
05-02-2021 - |
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.
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.