{"id":"W2018207776","doi":"10.1016/j.ipl.2007.01.007","title":"Average-case analysis of QuickSort and Binary Insertion Tree height using incompressibility","year":2007,"lang":"en","type":"article","venue":"Information Processing Letters","topic":"Computability, Logic, AI Algorithms","field":"Computer Science","cited_by":2,"is_retracted":false,"has_abstract":false,"ca_institutions":"University of Waterloo","funders":"Center for Advanced Study, University of Illinois at Urbana-Champaign; Natural Sciences and Engineering Research Council of Canada; Tsinghua University; National Science Foundation","keywords":"Quicksort; Binary tree; Computer science; Tree (set theory); Mathematics; Parallel computing; Algorithm; Combinatorics; Sorting; Sorting algorithm","routes":{"ca_aff":true,"ca_fund":true,"ca_venue":false,"about_ca":false,"invisible_to_affiliation_only":false},"retraction":null,"screen":null,"direct_labels":[],"prediction":{"model_version":"codex-gemma-dda1882f352a","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.001223657,0.0001678368,0.0002848255,0.0008513806,0.0002261675,0.0002372645,0.00031934,0.00007482355,0.000004768805],"category_scores_gemma":[0.00006885119,0.0001583341,0.00008900202,0.001893109,0.0001271846,0.004171539,0.0002435913,0.0001407973,0.000001591764],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.0001318672,"about_ca_system_score_gemma":0.00006447944,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.0001212534,"about_ca_topic_score_gemma":0.0000206084,"domain_scores_codex":[0.9982021,0.00006169483,0.0008283383,0.0002629862,0.0003870403,0.0002578248],"domain_scores_gemma":[0.9986414,0.0001197722,0.0004956586,0.0004226306,0.0002264067,0.0000940856],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"design_other","study_design_gemma":"simulation_or_modeling","study_design_scores_codex":[0.000084603,0.0002259115,0.07689373,0.0006345563,0.0002576906,0.0001275792,0.01730007,0.08924661,0.01032793,0.0002986837,0.00004426559,0.8045584],"study_design_scores_gemma":[0.0002624047,0.00002753602,0.1148128,0.00002537,0.0000634872,0.0001137171,0.00009701268,0.8829665,0.001269857,0.0001291802,0.00005253021,0.0001795343],"study_design_candidate":"simulation_or_modeling","study_design_consensus":null,"genre_codex":"empirical","genre_gemma":"empirical","genre_scores_codex":[0.5044126,0.00002277958,0.4951187,0.0001585001,0.00006168403,0.00008780233,0.000001605781,0.00007149995,0.00006479863],"genre_scores_gemma":[0.9262652,9.598442e-7,0.07289834,0.0007979888,0.00002020099,0.000002480823,0.00001027801,0.00000359862,9.503245e-7],"genre_candidate":"empirical","genre_consensus":"empirical","teacher_disagreement_score":0.8043788,"threshold_uncertainty_score":0.6456679,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.01726773757064013,"score_gpt":0.2616361200931165,"score_spread":0.2443683825224764,"validation_status":"score_only:v0-immature-baseline","note":"Baseline scores from an immature model (maturity gate not passed). Scores rank; they never assert a category."}}