How reason that an algorithm has n*logn time complexity?

[Pithikos]

Some time ago I wrote an exam where I had to write a pseudocode to sort elemens in a list. I used a quicksort with the pivot in the middle and wrote that the algorithm has time complexity in best case O(n*logn) because it is a divide-and-conquer algorithm. That didn't satisfy my teacher and he noted to me that not all divide-and-conquer algorithms have n*logn.
So how would someone reason about this? (Taking quicksort as en example)

 

[rcgldr]

You'd either have to add counters for the number of operations done in quicksort program and actually run it with some test sets of data, or generate a mathematical equation for the number of operations done by analyzing a quicksort program. I'm not aware of any generic method that would apply to all divide and conquer algorithms.

On a side note, an alternative to quicksort is a merge sort, but it uses more memory (double if sorting values, double the number of pointers if sorting an array of pointers to objects).

Previous threads on sorting. I included some test results in post #16 of the thread in the first link:

https://www.physicsforums.com/showthread.php?t=218369

https://www.physicsforums.com/showthread.php?t=181589

 

[chiro]

Some time ago I wrote an exam where I had to write a pseudocode to sort elemens in a list. I used a quicksort with the pivot in the middle and wrote that the algorithm has time complexity in best case O(n*logn) because it is a divide-and-conquer algorithm. That didn't satisfy my teacher and he noted to me that not all divide-and-conquer algorithms have n*logn.
So how would someone reason about this? (Taking quicksort as en example)

If you want to figure out the runtime complexity of an algorithm, the best way is to look at the execution nesting within the algorithm.

For example let's say you have two loops, both go from 1 to some variable n. The run-time is going to be O(n^2). Also note that run-time is typically "worst-case" unless otherwise specified.

You basically use nesting as a hint for creating another factor. Look at the bounds of each loop and use that information to create your complexity factor.

The same also applies if you use recursion. The same idea is applied, although its typically more complex and you have to keep track of more variables (think memory state) when doing the analysis.

So in a nutshell translate all loops/recursive calls with boundary information to nested factors and use factors to generate complexity bound.