Algorithm analysis

  • Thread starter kioria
  • Start date
  • #1
kioria
53
0
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 [tex]A_{k}[/tex] 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 [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.
 

Answers and Replies

  • #2
ComputerGeek
383
0
kioria said:
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 [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.

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

Suggested for: Algorithm analysis

Replies
1
Views
397
  • Last Post
Replies
5
Views
636
Replies
14
Views
889
Replies
9
Views
2K
  • Last Post
Replies
2
Views
859
Replies
6
Views
443
Replies
17
Views
785
  • Last Post
Replies
10
Views
2K
  • Last Post
Replies
1
Views
1K
Top