Algorithm Analysis: Sorting Arrays in A_k with Constant Cn

[kioria]

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 $$A_{k}$$ 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 $$A_{k}$$ can be sorted in time $$Cn$$.

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.

 

[ComputerGeek]

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 $$A_{k}$$ 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 $$A_{k}$$ can be sorted in time $$Cn$$.

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.

it is just asking that given the parameters show that the time complexity is O(n) or linear.