Analyze Code

Determine \Theta for the following code fragment in the average case. Assume that all variables are of type "int". Assume array A contains a random permutation of the values from 0 to n-1.

              sum = 0;
              for (i = 0; i < n; i++) {
                for (j = 0; A[j] != i; j++)
                  sum++;
              }

\Theta(n^2)

\Theta(\log n)
\Theta(n^2 \log n)
\Theta(1)
\Theta(n)
\Theta(n \log n)
\Theta(n^3)
\Theta(2^n)

How much work is done by the body of the inner for loop?

How many times is the inner for loop executed? Multiply this by the amount of work done by the body.

How many times is the outer for loop executed? Multiply this by the amount of work done by the inner for loop.