Login
Login

Wikipedia:Reference desk/Archives/Computing/2016 August 23

{{#ifeq:{{PAGENAME}}|Special:Undelete| |{{#if:|

}} {{#ifeq:{{NAMESPACE}}|Wikipedia|{{#switch:{{NAMESPACE}}|= |
}}|{{error:not substituted|Archive header}}
}}}} {{#if:|
}}
width = "100%"
colspan="3" align="center" | Computing desk
width="20%" align="left" | < August 22

! width="25%" align="center"|<< Jul | August | Sep >>

! width="20%" align="right" |{{#ifexist:Wikipedia:Reference desk/Archives/Computing/2016 August 24|August 24|Current desk}} >

align=center width=95% style="background: #FFFFFF; border: 1px solid #003EBA;" cellpadding="8" cellspacing="0"
style="background: #5D7CBA; text-align: center; font-family:Arial; color:#FFFFFF;" | Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is {{#ifexist:Wikipedia:Reference desk/Archives/Computing/2016 September 2|an archive page|a transcluded archive page}}. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

__TOC__

= August 23 =

[[median of medians]]

Hello,

In the median of medians algorithm, how come we use a single recurrence relation for the complexity of the entire algorithm, although we have two different functions that are mutually recursive?

Thanks — Preceding unsigned comment added by 2.53.63.189 (talk) 19:36, 23 August 2016 (UTC)

:You likely want the "Proof of O(n) running time" section in the article that you linked. 209.149.113.4 (talk) 17:21, 24 August 2016 (UTC)