{"id":"W2074047803","doi":"10.1007/s11390-010-9407-0","title":"Formally Analyzing Expected Time Complexity of Algorithms Using Theorem Proving","year":2010,"lang":"en","type":"article","venue":"Journal of Computer Science and Technology","topic":"Logic, Reasoning, and Knowledge","field":"Computer Science","cited_by":5,"is_retracted":false,"has_abstract":false,"ca_institutions":"Concordia University","funders":"","keywords":"Computer science; Probabilistic analysis of algorithms; Mathematical proof; Theory of computation; Computational complexity theory; Algorithm; Automated theorem proving; Probabilistic logic; Time complexity; Descriptive complexity theory; Theoretical computer science; Mathematics; Artificial intelligence","routes":{"ca_aff":true,"ca_fund":false,"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.001495035,0.0001347287,0.0003540919,0.001000902,0.000272513,0.0001657278,0.001884451,0.00011133,0.000004246373],"category_scores_gemma":[0.0001597566,0.0001004291,0.00006136505,0.001809983,0.001533606,0.001129848,0.0007825614,0.0004211784,0.000001647152],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.00003332437,"about_ca_system_score_gemma":0.0004534442,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.000004387438,"about_ca_topic_score_gemma":0.00000319787,"domain_scores_codex":[0.9984788,0.00002807379,0.0004614643,0.0002691895,0.0004081437,0.0003543714],"domain_scores_gemma":[0.9976897,0.00005995231,0.000584359,0.0003842264,0.001166257,0.00011547],"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.00001048539,0.0001886394,0.007531199,0.0000245127,0.00004497833,0.00007095403,0.001333933,0.00003953443,0.3037099,0.3082057,0.0000539208,0.3787863],"study_design_scores_gemma":[0.0007090897,0.0007732797,0.004755891,0.00009015767,0.00002100462,0.002669968,0.00005282956,0.8580911,0.0627527,0.06950945,0.0002714366,0.0003031282],"study_design_candidate":"simulation_or_modeling","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.4965872,0.00008237734,0.5024092,0.0002906237,0.0003718254,0.00004953426,2.106902e-7,0.00004357989,0.00016547],"genre_scores_gemma":[0.6695237,0.000004544494,0.3303601,0.00002270581,0.00008258147,2.70478e-7,3.839323e-8,0.000002903124,0.000003211485],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.8580515,"threshold_uncertainty_score":0.5650637,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.01665396761359184,"score_gpt":0.2521595947787549,"score_spread":0.235505627165163,"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."}}