Avgerage Time Complexity of a sorting algorithm

I have a treesort function which performs two distinct tasks, each with its own time complexity. I figured out the avg. case time complexity of the two tasks but how do I find the overall complexity of the algorithm.

For example the algorithm takes in a random list of "n" keys x:

Sort(x):
    Insert(x):
        #Time complexity of O(nLog(n))
    Traverse(x):
        #Time complexity of O(n)

Do I just add the two complexities together to give me O(n + nLog(n)) or do I take the do开发者_JAVA百科minant task (in this case Insert) and end up with an overall complexity of O(nLog(n))

In a simple case like this,

O((n) + (n log(n)) = O(n + n log(n))
                  = O(n (log(n) + 1))
                  = O(n log(n))

or do I take the dominant task (in this case Insert) and end up with an over complexity of O(nLog(n))
That's right. As n grows, first element in O(n + nLog(n)) sum will become less and less significant. Thus, for sufficiently large n, its contribution can be ignored.

You need to take the dominant one.

The whole idea of measuring complexity this way is based on the assumption that you want to know what happens with large ns.

So if you have a polynomial, you can discard all but the highest order element, if you have a logarithm, you can ignore the base and so on.

In everyday practice however, these differences may start to matter, so it's sometimes good to have a more precise picture of your algorithm's complexity, even down to the level where you assign different weights to different operations.

(Returning to your original questions, assuming you're using base 2 logarithms, at n=1048576, the difference between n+n*logn and n*logn is around 5%, which is probably not really worth worrying about.)