Which of the following is NOT relevant to the sorting problem lower bounds proof?

The worst-case cost for Bubble Sort is \Theta(n^2)
  • The number of permutations for n records is n!
  • A tree with n nodes has a depth of at least \log n
  • Any sorting algorithm can be modeled using a decision tree

The proof uses decision trees to model sorting algorithms.

The number of permutations affects the size of the decision tree.

Given a tree of a certain size, we can compute its minimum depth.

The cost of Bubble Sort does not affect the cost of other sorts.