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

{| 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" |Current desk > |}

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is 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.

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)