CODEWITHSUNDEEP
algorithmtime-complexity
Yoda
Yoda

Reputation: 18068

How the average complexity is calculated

How the average complexity of algorithm is calculated? Worst is obvious, best also, but how the average is calculated?

Upvotes: 0

Views: 226

Answers (3)

Gene
Gene

Reputation: 46960

Average performance (time, space, etc.) complexity is found by considering all possible inputs of a given size and stating the asymptotic bound for the average of the respective measure across all those inputs.

For example, average "number of comparisons" complexity for a sort would be found by considering all N! permutations of input of size N and stating bounds on the average number of comparisons performed across all those inputs.

I.e. this is the sum of numbers of comparisons for all of the possible N! inputs divided by N!

Because the average performance across all possible inputs is equal to the expected value of the same performance measure, average performance is also called expected performance.

Upvotes: 2

Vikram Bhat
Vikram Bhat

Reputation: 6246

calculate the complexity for all possible input and take and weighted sum based on their probabilities. This is also called expected runtine (similar to expectation in probabilities).

ET(I) = P(X=I1)*T(I1) + P(X=I2)*T(I2) + P(X=I3)*T(I3).......

Upvotes: 2

Zim-Zam O'Pootertoot
Zim-Zam O'Pootertoot

Reputation: 18148

Quicksort presents an interesting non-trivial example of calculating the average run-time performance. As you can see the math can get quite complex, and so unfortunately I don't think there's a general equation for calculating average performance.

Upvotes: 0

Related Questions