Is this right? Finding big theta

nguyeng · 09-08-2012, 08:48 PM

Hello all, I'm doing some studying for an exam that I will have on Monday and was going over some practice problems. I'm not sure if I was able to grasp the concept of asymptotic analysis well enough. I would just like to check my answer and explain my thought process behind getting the answers to see if I'm doing these correctly. I would ask my professor but it is the weekend and the exam is first thing in the morning on Monday. Thanks for the help.

Determine big theta for the following code fragments in the average case. Assume
that all variables are of type int.

(h) Assume array A contains a random permutation of the values from 0 to
n - 1.

Code:

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

Outer loop will be executed n times. Inner loop is executed n/2 times on average. So, bigTheta(n(n/2)) simplified to bigTheta(n^2).

(i)

Code:

sum = 0;
if (EVEN(n))for (i=0; i<n; i++)
sum++;
else
sum = sum + n;

If n is even then n executions, else 1. Seeing that n will be even half of the time. The average should be both clauses averaged which is (n+1)/2, which is bigTheta(n).

ntubski · 09-09-2012, 06:26 AM

Looks good to me.

PS it seems like using [INDENT] tags inside [CODE] boxes makes the [CODE] boxes tiny, you can just use whitespace to indent inside [CODE] boxes:

Code:

sum = 0;
if (EVEN(n))
   for (i=0; i<n; i++)
      sum++;
else
   sum = sum + n;

nguyeng · 09-09-2012, 08:10 AM

Cool. Thanks for the assistance!