Avgerage Time Complexity of a sorting algorithm

Question

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 dominant task (in this case Insert) and end up with an overall complexity of O(nLog(n))

Nikita Rybak · Accepted Answer · 2011-02-09 01:11:10Z

7

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))

edited Feb 9, 2011 at 1:11

Nikita Rybak

68.1k22 gold badges163 silver badges183 bronze badges

answered Feb 9, 2011 at 0:49

Pointy

415k62 gold badges600 silver badges631 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Nikita Rybak · Accepted Answer · 2011-02-09 00:48:07Z

2

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.

answered Feb 9, 2011 at 0:48

Nikita Rybak

68.1k22 gold badges163 silver badges183 bronze badges

Comments

biziclop · Accepted Answer · 2011-02-09 00:54:49Z

2

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.)

edited Feb 9, 2011 at 0:54

answered Feb 9, 2011 at 0:48

biziclop

50k12 gold badges80 silver badges108 bronze badges

Collectives™ on Stack Overflow

Avgerage Time Complexity of a sorting algorithm

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related