Timeline for Why Does the Deterministic Selection Algorithm Run in $O(n)$ and not $O(n\log n)$?
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Mar 12, 2016 at 15:53 | history | suggested | wythagoras | CC BY-SA 3.0 |
use of LaTeX
|
| Mar 12, 2016 at 13:26 | review | Suggested edits | |||
| S Mar 12, 2016 at 15:53 | |||||
| Mar 12, 2016 at 7:31 | history | edited | Raphael |
edited tags
|
|
| Mar 12, 2016 at 7:03 | vote | accept | justAnotherGuy | ||
| Mar 12, 2016 at 6:57 | history | edited | David Richerby | CC BY-SA 3.0 |
title
|
| Mar 12, 2016 at 6:10 | vote | accept | justAnotherGuy | ||
| Mar 12, 2016 at 6:22 | |||||
| Mar 12, 2016 at 5:43 | answer | added | Sarvottamananda | timeline score: 3 | |
| Mar 12, 2016 at 5:43 | comment | added | justAnotherGuy | And there are log many recursive calls because if you do a call each time you cut the size in half (as in binary search), you do log many calls, and this is only guaranteed to cut down the size by .7 each call, which is greater than "in half", so you would do (at least) log many calls. | |
| Mar 12, 2016 at 5:28 | comment | added | justAnotherGuy | Further: the recurrence relation for binary search is T(n) = T(n/2) + 1, which "telescoped" is "O(log(n))". The given recurrence relation for this algorithm is T(n) <= 12/5n + T(n/5) + T(7n/10). Telescoping in the same way each T(7n/10) term would have an n term plus a T(n/5) term and plus a T(7n/10) term until base case. So it seems this relation "telescopes" to something like T(n) <= n + nlog(n) even discarding the (n/5) term, which is T(n) <= n*log(n) | |
| Mar 12, 2016 at 5:11 | comment | added | justAnotherGuy | Hi. I'm not sure, but conceptually the algorithm seems like "cut the search area like binary search, but maybe not by as much as binary search, and add a linear time partition." Binary search runs in O(log(n)). So this would run in O(n*log(n)). The two analyses are opposed. What is wrong with this analysis compared to the recurrence relation presented? | |
| Mar 12, 2016 at 5:09 | history | edited | justAnotherGuy | CC BY-SA 3.0 |
added 362 characters in body
|
| Mar 12, 2016 at 5:08 | comment | added | D.W.♦ |
What do you think the recurrence relation should be? Why do you think there are log many recursive calls? Syntactically, I only see two: select(L1,k) and select(L3,k-length(L1)-length(L2)). Also, please proof-rad your formatting and indent/spacing.
|
|
| Mar 12, 2016 at 4:53 | history | asked | justAnotherGuy | CC BY-SA 3.0 |