Search code examples
algorithmsortingbig-ologarithm

What is the running time of an O(n log n) sort done n times?

Is it O(n^2 log n)? Can you show how it is derived? Is O(n^2 log n) the same as O((n^2) * (log n))?

Solution

  • Doing something n times takes O(n) time. And n log n is just another way of writing n * log n So we get:

      O(n) * O(n * log n)
= O((n) * (n * log n)) 
= O(n * n * log n)
= O(n^2 * log n)

    Yes, the two ways of writing it that you have shown are the same. This is, however, something completely different: O(n^(2 log n))