notesum.ai

Published at October 20

CASET: Complexity Analysis using Simple Execution Traces for CS* submissions

cs.AI

cs.CL

Released Date: October 20, 2024

Authors: Aaryen Mehta¹, Gagan Aryan

Aff.: ¹Indian Institute of Technology Kanpur

Arxiv: https://arxiv.org/abs/2410.15419v1

Algorithm	Equation	a	b	c	d	MSE
Linear Search	$ax+b$	$4.47\times 10^{2}$	$1.28\times 10^{3}$	-	-	$4.96\times 10^{-25}$
Linear Search	$a\log(x+b)+c$	-	-	-	-	NA*
Binary Search	$ax+b$	$3.04\times 10^{2}$	$6.56\times 10^{3}$	-	-	$1.80\times 10^{6}$
Binary Search	$a\log(x+b)+c$	$3.37\times 10^{4}$	$6.36\times 10^{1}$	$-1.37\times 10^{5}$	-	$7.06\times 10^{5}$
Bubble Sort	$ax^{2}+bx+c$	$3.85\times 10^{2}$	$2.19\times 10^{1}$	$1.89\times 10^{3}$	-	$3.55\times 10^{9}$
Bubble Sort	$ax+b$	$4.01\times 10^{4}$	$-7.33\times 10^{5}$	-	-	$8.88\times 10^{10}$
Bubble Sort	$(ax+b)(\log(cx+d))$	-	-	-	-	NA*
Iterative Merge Sort	$ax+b$	$1.55\times 10^{4}$	$-7.68\times 10^{4}$	-	-	$8.45\times 10^{8}$
Iterative Merge Sort	$(ax+b)(\log(cx+d))$	$1.70\times 10^{3}$	$-2.23\times 10^{3}$	$7.95\times 10^{1}$	$-7.93\times 10^{1}$	$5.33\times 10^{8}$
Iterative Merge Sort	$ax^{2}+bx+c$	$2.13\times 10^{1}$	$1.33\times 10^{4}$	$-3.61\times 10^{4}$	-	$5.85\times 10^{8}$
Recursive Merge Sort	$ax+b$	$2.58\times 10^{4}$	$-2.14\times 10^{5}$	-	-	$3.90\times 10^{9}$
Recursive Merge Sort	$(ax+b)(\log(cx+d))$	$7.75\times 10^{3}$	$-1.26\times 10^{4}$	$2.12\times 10^{-1}$	$4.39\times 10^{0}$	$3.17\times 10^{7}$
Recursive Merge Sort	$ax^{2}+bx+c$	$8.11\times 10^{1}$	$1.74\times 10^{4}$	$-5.95\times 10^{4}$	-	$1.35\times 10^{9}$
Recursive Fibonacci	$e^{ax+b}+c$	$5.40\times 10^{-1}$	$6.28\times 10^{0}$	$-1.85\times 10^{3}$	-	$1.45\times 10^{6}$
Recursive Fibonacci	$ax+b$	$8.45\times 10^{4}$	$3.96\times 10^{5}$	-	-	$1.01\times 10^{11}$
DP Fibonacci	$e^{ax+b}+c$	-	-	-	-	NA*
DP Fibonacci	$ax+b$	$3.23\times 10^{2}$	$7.71\times 10^{0}$	-	-	$2.41\times 10^{-25}$
DP Rod Cutting Problem	$ax^{2}+bx+c$	$3.74\times 10^{2}$	$7.99\times 10^{2}$	$2.11\times 10^{3}$	-	$5.68\times 10^{3}$
DP Rod Cutting Problem	$e^{ax+b}+c$	$1.01\times 10^{1}$	$9.47\times 10^{0}$	$-1.24\times 10^{4}$	-	$1.07\times 10^{5}$
Recursive Rod Cutting Problem	$ax^{2}+bx+c$	$5.07\times 10^{4}$	$-3.67\times 10^{5}$	$5.09\times 10^{5}$	-	$4.17\times 10^{10}$
Recursive Rod Cutting Problem	$e^{ax+b}+c$	$7.67\times 10^{-1}$	$7.072\times 10^{0}$	$-1.17\times 10^{3}$	-	$5.34\times 10^{6}$
DP Edit Distance Problem	$e^{ax+b}+c$	$-6.01\times 10^{1}$	$6.48\times 10^{0}$	$4.15\times 10^{5}$	-	$1.28\times 10^{11}$
DP Edit Distance Problem	$ax^{2}+bx+c$	$1.37\times 10^{4}$	$-3.17\times 10^{4}$	$6.12\times 10^{4}$	-	$5.59\times 10^{8}$
Recursive Edit Distance Problem	$e^{ax+b}+c$	$1.71\times 10^{0}$	$8.15\times 10^{0}$	$7.21\times 10^{2}$	-	$5.11\times 10^{5}$
Recursive Edit Distance Problem	$ax^{2}+bx+c$	$6.46\times 10^{5}$	$2.20\times 10^{6}$	$1.67\times 10^{6}$	-	$3.99\times 10^{10}$