# Algorithm analysis

1. Aug 29, 2005

### 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 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 $$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.

2. Aug 30, 2005

### ComputerGeek

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