Algorithm analysis

  • Thread starter kioria
  • Start date
52
0

Main Question or Discussion Point

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

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

Related Threads for: Algorithm analysis

  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
5
Views
14K
  • Last Post
Replies
1
Views
2K
Replies
3
Views
6K
  • Last Post
Replies
8
Views
2K
Top