Kth Order Statistic: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
(Created page with "{{DISPLAYTITLE:kth Order Statistic (kth Order Statistic)}} == Description == An algorithm seeks to find the $k^{th}$ order statistic of a statistical sample, or the $k^{th}$-smallest value in a list or array. == Parameters == <pre>n: size of list</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference |- | Naive Selection (kth Order St...")
 
No edit summary
 
(3 intermediate revisions by the same user not shown)
Line 6: Line 6:
== Parameters ==  
== Parameters ==  


<pre>n: size of list</pre>
$n$: size of list


== Table of Algorithms ==  
== Table of Algorithms ==  
Line 16: Line 16:
|-
|-


| [[Naive Selection (kth Order Statistic kth Order Statistic)|Naive Selection]] || 1940 || $O(nlogn)$ || $O({1})$ (can use in-situ sorting) || Exact || Deterministic ||   
| [[Naive Selection (kth Order Statistic kth Order Statistic)|Naive Selection]] || 1940 || $O(n \log n)$ || $O({1})$ (in-situ) || Exact || Deterministic ||   
|-
|-
| [[Hoare's Selection Algorithm (QuickSelect) (kth Order Statistic kth Order Statistic)|Hoare's Selection Algorithm (QuickSelect)]] || 1961 || $O(n)$ || $O({1})$ (in-situ) || Exact || Deterministic || [https://dl.acm.org/citation.cfm?doid=366622.366647 Time]
| [[Hoare's Selection Algorithm (QuickSelect) (kth Order Statistic kth Order Statistic)|Hoare's Selection Algorithm (QuickSelect)]] || 1961 || $O(n^{2})$ || $O({1})$ (in-situ) || Exact || Deterministic || [https://dl.acm.org/citation.cfm?doid=366622.366647 Time]
|-
|-
| [[Hashing (kth Order Statistic kth Order Statistic)|Hashing]] || 1940 || $O(n)$ || $O(n)$ || Exact || Deterministic ||   
| [[Hashing (kth Order Statistic kth Order Statistic)|Hashing]] || 1940 || $O(n)$ || $O(n)$ || Exact || Deterministic ||   
Line 24: Line 24:
|}
|}


== Time Complexity graph ==  
== Time Complexity Graph ==  


[[File:kth Order Statistic - Time.png|1000px]]
[[File:kth Order Statistic - Time.png|1000px]]
== Space Complexity graph ==
[[File:kth Order Statistic - Space.png|1000px]]
== Pareto Decades graph ==
[[File:kth Order Statistic - Pareto Frontier.png|1000px]]


== References/Citation ==  
== References/Citation ==  


https://11011110.github.io/blog/2007/10/09/blum-style-analysis-of.html
https://11011110.github.io/blog/2007/10/09/blum-style-analysis-of.html

Latest revision as of 09:04, 28 April 2023

Description

An algorithm seeks to find the $k^{th}$ order statistic of a statistical sample, or the $k^{th}$-smallest value in a list or array.

Parameters

$n$: size of list

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Naive Selection 1940 $O(n \log n)$ $O({1})$ (in-situ) Exact Deterministic
Hoare's Selection Algorithm (QuickSelect) 1961 $O(n^{2})$ $O({1})$ (in-situ) Exact Deterministic Time
Hashing 1940 $O(n)$ $O(n)$ Exact Deterministic

Time Complexity Graph

Kth Order Statistic - Time.png

References/Citation

https://11011110.github.io/blog/2007/10/09/blum-style-analysis-of.html