{"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":"metacan-v3-hybrid-931329e0061c","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.01002224,0.00124894,0.002520974,0.006222568,0.001982614,0.004746707,0.006682778,0.002716695,0.01059631],"category_scores_gemma":[0.08324634,0.001216584,0.001429067,0.007306066,0.00478407,0.0190403,0.00299708,0.003367089,0.000737599],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.004240339,"about_ca_system_score_gemma":0.002988535,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.004256595,"about_ca_topic_score_gemma":0.004287078,"domain_scores_codex":[0.9930864,0.001544929,0.0003336584,0.00103615,0.002396597,0.001602329],"domain_scores_gemma":[0.8753648,0.1022792,0.005764809,0.008488218,0.005177963,0.002924983],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"simulation_or_modeling","study_design_gemma":"theoretical_or_conceptual","study_design_scores_codex":[0.0007466107,0.0002889232,0.006557367,0.0003104626,0.0001189414,0.0005767829,0.000348616,0.5155241,0.00356524,0.4298448,0.004674954,0.03744325],"study_design_scores_gemma":[0.000015376,0.00004304836,0.0006576087,0.00001563121,0.00003896884,0.0002011495,0.00004882202,0.9071916,0.001155077,0.0902165,0.0003920824,0.00002404781],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.4584079,0.004354603,0.5081939,0.002575232,0.0002321843,0.00009942846,0.00080152,0.002027725,0.02330755],"genre_scores_gemma":[0.9658373,0.0005952583,0.02923755,0.0001517206,0.0003311785,0.0000511518,0.000302511,0.0004109373,0.003082393],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.01059631,"threshold_uncertainty_score":0.05300331,"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."}}