- 52

- 0

## Main Question or Discussion Point

In the problems below A[1, ...,

1) Let

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.

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