CSE 373 Winter 2013 Homework 7: Sort Detective, Part A John Doe This assignment is about ... Algorithm #1 --- Algorithm N order time(ms) ----------------------------------------------------- #1 1000 Random 79 #1 2000 Random 219 #1 4000 Random 681 #1 8000 Random 1842 #1 1000 Ascending 50 #1 2000 Ascending 102 #1 4000 Ascending 153 #1 8000 Ascending 198 #1 1000 Descending 102 #1 2000 Descending 398 #1 4000 Descending 1443 #1 8000 Descending 5017 Big-Oh: O(N^47) Conclusion: This is FooBar sort. I can tell because the runtime goes up by roughly X.Y every time I double N, and X.Y is approximately 2^K, which means that the growth rate is proportional to the Kth power of the input size N, so the Big-Oh is O(N^K). The runtimes are different by approximately X% when ascending input is passed in, which is consistent with the algorithm because it does not need to swap as many doohickeys into the thingamabob when it is ascending. Also it crashed when I set N = 16000, which is consistent with the XYZ property of FooBar sort, and it is slower than Algorithm #7, which must be BarBaz sort, the slower of the two O(N^47) algorithms we covered in class. Algorithm #2 --- ... (and so on)