- #1

kioria

- 53

- 0

*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

*i*≤

*n*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.