In the problems below A[1, ...,(adsbygoogle = window.adsbygoogle || []).push({}); n] denotes an array consisting of arbitrarynreal numbers, and A[j] denotes the element in thej-th place of the array A[1, ...,n].

1) Letkbe a fixed natural number. Consider the family [tex]A_{k}[/tex] of all arrays A[1, ...,n] satisfying that for everyi≤nthere are at mostkelements 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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Algorithm analysis

**Physics Forums | Science Articles, Homework Help, Discussion**