Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Algorithm analysis

  1. Aug 29, 2005 #1
    In the problems below A[1, ..., n] denotes an array consisting of arbitrary n real numbers, and A[j] denotes the element in the j-th place of the array A[1, ..., n].

    1) Let k be a fixed natural number. Consider the family [tex]A_{k}[/tex] of all arrays A[1, ..., n] satisfying that for every in there are at most k elements among A[1, ..., (i - 1)] larger than A[i]. Show that there exists a constant C such that every array A[1, ..., n] from [tex]A_{k}[/tex] can be sorted in time [tex]Cn[/tex].

    nb. This seems like a simple question, I just need to adapt to the style of approaching these types of questions. Your help will be greatly appreciated.
  2. jcsd
  3. Aug 30, 2005 #2
    it is just asking that given the parameters show that the time complexity is O(n) or linear.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook