I've asked the same question on a specific algorithm, the insertion sort, but I've got no feedback from it.

Basically i think that you have to somehow calculate the complexity of each instance of your problem, then group the cases that have the same complexity, plot the different complexities and do something like a weighted average. Of course the case of insertion sort was more interesting then talking in general, since permutations are known groups and i thought that an easy way to figure how many different complexities you have, and how many cases of each complexity is by doing something with equivalence classes.

  • $\begingroup$ I think this question has to be more specific, since complexity analysis depends on the problem and algorithm. Here is a very simple example where worst case complexity is $n^2$ but average complexity is roughly $2n$: Problem: Let $A$ be an $n \times n$ binary matrix with iid Bernoulli entries with $P[a_{ij}=1]=P[a_{ij}=0]=1/2$. We want to know how many columns are nonzero. Algorithm: We search each column row-by-row. The first time we find a "1" in a column, increase the tally by 1 and go to the next column (we determine the column has no 1s if we search each of its rows). $\endgroup$
    – Michael
    Oct 26, 2016 at 22:19
  • $\begingroup$ Worst-case complexity for this algorithm is $n^2$, which is achieved by the all-zero matrix $A=0$ (since we have to search each row of each column). Average case for a randomly chosen $A$ is slightly better than $2n$, since on average we find the first "1" in a column after (almost) 2 row searches. $\endgroup$
    – Michael
    Oct 26, 2016 at 22:21
  • $\begingroup$ Thank you kind sir for actually caring to comment. I have firstly posted the question on a specific algorithm, the insertion sort, as I've mentioned, but I've been ignored. I thought that because the problem was so specific, people felt like it was some sort of homework question... although they would have down-voted in that case. I frankly don't know. The link to the previous question is: math.stackexchange.com/questions/1982162/… $\endgroup$
    – Hemispherr
    Oct 26, 2016 at 22:25


You must log in to answer this question.

Browse other questions tagged .