I'm running experiements that record the time my algorithm takes to solve a set of problem instances on a particular benchmark. Each problem has an associated difficulty in the range [1, n]. Ideally these should be evenly distributed across the difficulty spectrum but this is not the case: the problem sample I have is skewed toward the easier end of the spectrum.
To account for this, I have grouped the problems by difficulty e.g. [1-10], [11-20], ... , [n-9, n]. Each interval usually contains contains at least 10 problems (usually more; 50+ is not uncommon) and I take the average time required to solve all problems in each interval. This gives me a clearer picture of how my algorithm performs on both easy and hard problems with the caveat that the data is somewhat less reliable for the harder end of the spectrum.
First question: is this okay or are there some gotchas I haven't accounted for?
Next: For comparative purposes, I need to summarise performance on each benchmark as a single number. I am loath to simply take the average across all problems as this figure is skewed by too many easy problems. Which brings me to...
Second question: can I take an average of all interval averages instead?