CODEWITHSUNDEEP
c++algorithmcomplexity-theorybig-o
user7804781
user7804781

Reputation: 316

Predict an algorithm's theoretical average-case efficiency and order of growth using summation

I need to predict the algorithm's average case efficiency with respect to the size of its inputs using summation/sigma notation to arrive at the final answer. Many resources use summation to predict worst-case, and I couldn't find someone explaining how to predict average case so step-by-step answers are appreciated.

The algorithm contains a nested for loop, with the basic operation inside the innermost loop:

[code redacted]

EDIT: The execution of the basic operation it will always execute inside the second for loop if the second for loop has been entered, and has no break or return statements. HOWEVER: the end of the first for loop has the return statement which is dependent on the value produced in the basic operation, so the contents of the array do affect how many total times the basic operation will be executed for each run of the algorithm.

The array passed to the algorithm has randomly generated contents

I think the predicted average case efficiency is (n^2)/2, making it n^2 order of growth/big Theta of n^2, but I don't know how to theoretically prove this using summation. Answers are very appreciated!

Upvotes: 4

Views: 267

Answers (1)

alexeykuzmin0
alexeykuzmin0

Reputation: 6440

TL;DR: Your code complexity in average case is Θ(n²) if "basic operation" complexity is Θ(1) and it has no return, break or goto operators.

Explanation: the average-case complexity is just an expectation of the number of operations in your code given the size of the input.

Let's say T(A, n) is a number of operations your code performs given array A of size n. It's easy to see that

T(A, n) = 1  +                // int k = ceil(size/2.0);
    n * 2 + 1 +               // for (int i = 0; i < size; i++){
    n * (n * 2 + 1) +         // for(int j = 0; j < size; j++){
    n * n * X +               // //Basic operation 
    1                         // return (some int);

Where X is a number of operations in your "basic operation". As we can see, T(A, n) does not depend on actual contents of the array A. Thus, the expected number of operations given size of the array (which is simply the arithmetical mean of T(A, n) for all possible A for given n) is exactly equal to each of them:

T(n) = T(A, n) = 3 + n * 2 + n * n * (2 + X)

If we assume that X = Θ(1), this expression is Θ(n²).

Even without this assumption we can have an estimate: if X = Θ(f(n)), then your code complexity is T(n) = Θ(f(n)n²). For example, if X is Θ(log n), T(n) = Θ(n² log n)

Upvotes: 1

Related Questions