CODEWITHSUNDEEP
c++performancebig-ocomplexity-theory
AaySquare
AaySquare

Reputation: 123

How to calculate average asymptotic running time in Big-O notation?

Trying to understand Asymptotic notations which I understand is used to describe performance of an algorithm. Am I correct in saying that there is worst, best and average case scenarios? So for example, for the following piece of code, what is the average asymptotic running time in Big-O notation? 

for (int i = 0; i < size; i++)
{
    printf("%d\n", i);
}
for (int i = 0; i < size; i++)
{
    for (int j = 0; j < size; j++)
    {
        printf("%d\n", i + j);
    }
}

Would it be O(n^2)?

Upvotes: 0

Views: 871

Answers (2)

Patrick87
Patrick87

Reputation: 28302

Am I correct in saying that there is worst, best and average case scenarios?

A case is just some subset of all possible inputs, possibly a subset that has one input of all possible input sizes. So for instances, a case for a sorting algorithm might be some subset of the set of all possible input arrays, and maybe just those subsets that have exactly one element of each input size. Using this definition, the worst case would be the subset of inputs such that they cause the algorithm to execute the most instructions for the given input size; the best case would be the set of inputs that require the least number of steps at each input size; and the average case would be like the expected value of running types over all possible instances at each size (by the simple definition above, the average "case" is not really a true case at all, more like a hypothetical case).

To every case we may associate an asymptotic bound - upper, lower, or both. Typically of interest are upper bounds on the worst-case, and sometimes lower-bounds on the best-case. But it's not incorrect to speak of an upper bound on the best case or a lower bound on the worst case.

The code you've posted always does an amount of work proportional to the square of size's value. In that sense it is O(size^2). It is also Omega and Theta of size^2. If the algorithm gets input whose size in bits is proportional to size, then this is the true complexity. If the algorithm gets the value of size as input (represented using log(size) bits) then the complexity is actually exponential - the complexity in terms of size might be called pseudopolynomial.

Upvotes: 1

Blindy
Blindy

Reputation: 67380

Am I correct in saying that there is worst, best and average case scenarios?

Generally only worst case and average case are of interest, but you can consider the best case as well if you prefer.

Would it be O(n^2)?

What you have there is a typical O(n^2) complexity, yes. Best, average and worst, they're all the same for your particular case. They're only not the same if you can break out of loops early, or conditionally skip entire loops.

Edit: Example of when the average and best case complexity are different:

for(var i = 0; i < len; ++i) 
  if(arr[i] == needle)
    return needle;

This is at best a constant operation, ie O(1), if the element is found right away, and at worst an O(n) linear operation -- a linear search specifically.

Upvotes: 2

Related Questions