CODEWITHSUNDEEP
algorithmsortingtime-complexity
Antonino DG
Antonino DG

Reputation: 49

Worst Case minimum Sorting Time Complexity Theorem

I am studying sorting algorithms and I am stuck on the theorem that proves that a sorting algorithm on an n vector has ,at least, in the worst case a time complexity of

n*log2(n) + (1/2)*log2(n) - log2(e)*n + O(1)

Thee proof uses a Lemma which states that a binary tree with k leafs has an height of at least ceiling(log2(n)). The theorem states that you can build a binary decision tree with n! leafs and uses the Stirling formula to get to the result! It should be a classic theorem in the field of sorting algos.

My issue is that I can't figure out how the n! leaf binary tree is build! If for example we want to sort the vector v=(4,3,1) in increasing order how can I build the decision tree with 3!=6 leafs?

I apologize for possible mistakes and for not using math formulas properly.

Thanks in advance to everyone!

Upvotes: 0

Views: 280

Answers (2)

btilly
btilly

Reputation: 46389

Building that decision tree from a sorting algorithm is easy. Each comparison that the sorting algorithm could try divides the possible set of orders it could be into two groups. The sorting algorithm finishes when only one possible order is left.

You literally write out your possible decisions as a tree (<, >) into (left, right). Or up/down if you draw the tree sideways.

          a<b?
           |
     Y-----------N
     |           |
    b<c?        a<c?
     |           |
  Y-----N     Y-----N
  |     |     |     |
(abc)  a<c? (bac)  b<c?
        |           |
     Y-----N     Y-----N
     |     |     |     |
   (acb) (cab) (bca) (cba)

Now the unsolved in general question is this. What is the best possible decision tree? :-)

Upvotes: 1

yeputons
yeputons

Reputation: 9238

Here is one example:

if (v[0] <= v[1]) {
  if (v[1] <= v[2]) {
    // Sorted order: v[0], v[1], v[2]
  } else {
    // v[1] > v[2], so v[1] is a maximal element
    if (v[0] <= v[2]) {
      // Sorted order: v[0], v[2], v[1]
    } else {
      // Sorted order: v[2], v[0], v[1]
    }
  }
} else {
  // v[0] > v[1]
  if (v[1] > v[2]) {
    // Sorted order: v[2], v[1], v[0]
  } else {
    // v[1] <= v[2], so v[1] is a minimal element
    if (v[0] <= v[2]) {
      // Sorted order: v[1], v[0], v[2]
    } else {
      // Sorted order: v[1], v[2], v[0]
    }
  }
}

This decision tree has 6 leafs and it takes at most 3 decisions to reach the leaf.

And in general, how you actually build a decision tree is called "sorting algorithm". If you run an algorithm on all possible inputs, you can track how it makes decision about swapping elements and build corresponding decision tree.

Upvotes: 2

Related Questions