Algorithm analysis

  • Thread starter kioria
  • Start date
  • #1
52
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
379
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 on Algorithm analysis

  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
7
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
11
Views
3K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
2
Views
2K
Top