Printable View
Hello! This isn't really a Java question, but I created a Java program that does Insertion Sort, and my Java teacher wants me to find the average case for it. My teacher gave me a hint by saying that the answer is (1/4)(n^2) + (1/4)(n), but now he wants me to prove it. I'm not exactly sure how to do that; I even looked up various explanations online, but none have helped. So, is anyone willing to give me a clear, brief description of how that is the average case? Thanks in advance!
Mmm, probability :P
It's been a while since I've analyzed insertion sort, but if I remember correctly the performance time of Insertion Sort is proportional to the number of inversions. The more inversions, the less efficient the algorithm becomes. Unfortunately, I can't remember the math behind this.
There's a better description of this here: 6.6 Performance Characteristics of Elementary Sorts
That helped me a little bit, but unfortunately I still don't completely understand. Thanks anyway; I really appreciate it!