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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Algorithm analysis
  1. Circle algorithms (Replies: 1)

  2. A searching algorithm? (Replies: 7)

  3. RSA Algorithm (Replies: 2)

  4. Visual Basic/Algorithm (Replies: 1)