Algorithm Analysis Question

7    13 Feb 2016 08:00 by u/Meatfist

I am currently in a Comp Sci class and am math dumb. I realize CS is math heavy. The class does not have math prerequisites outside of some basic discrete mathematics. I'm also not incredibly concerned about the efficiency of the algorithm at the moment, so if the average number of comparisons seems high, that's OK.

After implementing a sorting algorithm, we were asked to run multiple tests on the number of comparisons being made and derive standard deviation and averages for various values of *n*.

For example, 210 ran 100 times had an average of around 15000 comparisons and a standard deviation of around 600. We are supposed to use our observed data to derive alpha and eta using equations given to us for (mean-2*n* ln*n*)/ (2 *n*) for alpha and (stddev)/*n* for eta and then use the alpha and eta estimates to see if our observed data matches estimates for averages and standard deviations.

I've been doing some reading and have found some sources that say alpha could (should?) be negative in most cases and am wondering whether the equation given for alpha is incorrect.

In a nutshell, I'm asking what is the proper way to derive alpha?

3 comments

1

I'm really sorry I don't have your answer, but I wanted to say you did an awesome job asking your question.

0

Thanks! I still appreciate the response. Probably going to go ahead and submit a bunch of wrong answers and then fight for points later by showing him I used his equations to reach my incorrect solutions.