bli0042's blog

Lower bounds of Omega(n log n)
By bli0042, 11 years ago, In English

  • Prove that the lower bound for any deterministic comparison-based sorting algorithm is (Well known) proof outline: model the comparisons as a binary decision tree; the bottom leaves are the n! permutations of the original sequence (one of which is the sorted). The height of the tree h satisfies 2^h >= n! so h >= log(n!) = Omega(n log n).

  • Consider the following problems:

  1. Given a sequence, determine if any two elements are equal.
  2. Given two sets, determine if they are equal.
  3. Given two sets, determine if they intersect.

Each has a simple solution by sorting and also a lower bound of Omega(n log n). Are there elementary proofs of this? (say, for a first-year algorithm analysis class)

The most similar to the one for sorting I found is this.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
11 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

This theorem give a very approximate result. So, for example, we have:

2h ≥ n! < nn,

h = log(n!), h ≤ log(nn),

now we will use one of basic logarithmic rules:

h ≤ n * log(n) Complexity = Ω(N * logN)

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you have inequality in wrong direction.

    you may say h = log (n!) < n! so

    h = \sigma (n!) and that's wrong.

    → Reply
»
11 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Problem 1 (Sorry for my bad English):
If we don't know how a[i] and a[j] compare (there is several options consistent with performed comparisons) then we can't know whether they are equal. But if such information is known about all possible pairs then we know the sorting order.
Is there any mistakes in this solution?

→ Reply