Before revision:  (i) The precise run time of the  on  . (ii) A lower bound for the run time of the  on  , tight apart from an O(n) term.
After revision:  (i) The precise run time of the  on . (ii) A lower bound for the run time of the   , tight apart from an O(n) term.