To what extent do the best, average and worst-case analyses (from class/textbook) of each sort agree with the experiment
Posted: Tue Jul 12, 2022 8:22 am
To what extent do the best, average and worst-caseanalyses (from class/textbook) of each sort agree with theexperimental results?
How do i graph this? I am not really sure on how to start this.To answer this question, you would need to find a way to comparethe experimental results for a sort with its predicted theoreticaltimes. One way to compare a time obtained experimentally to apredicted time of O(f(n)) (e.g., f(n)= n2 ) wouldbe to divide the time for a number of runs with different inputsizes by f(n) and see if you get a horizontal line (after someinput size n0). That n0 would representthe n0 value for the asymptotic analysis. The valueon the y-axis (assuming you put input size on the x-axis) will giveyou the constant value of the big-O. For each sort, and for eachcase (best, average, and worst), determine whether the observedexperimental running time is of the same order as predicted by theasymptotic analysis. Your determination should be backed up by yourexperiments and analysis and you must explain your reasoning. Ifyou found the sort didn't conform to the asymptotic analysis, youshould try to understand why and provide an explanation.
How do i graph this? I am not really sure on how to start this.To answer this question, you would need to find a way to comparethe experimental results for a sort with its predicted theoreticaltimes. One way to compare a time obtained experimentally to apredicted time of O(f(n)) (e.g., f(n)= n2 ) wouldbe to divide the time for a number of runs with different inputsizes by f(n) and see if you get a horizontal line (after someinput size n0). That n0 would representthe n0 value for the asymptotic analysis. The valueon the y-axis (assuming you put input size on the x-axis) will giveyou the constant value of the big-O. For each sort, and for eachcase (best, average, and worst), determine whether the observedexperimental running time is of the same order as predicted by theasymptotic analysis. Your determination should be backed up by yourexperiments and analysis and you must explain your reasoning. Ifyou found the sort didn't conform to the asymptotic analysis, youshould try to understand why and provide an explanation.