Determine the precise (i.e., not just the order of magnitude) Big-Oh values for

Question

Determine the precise (i.e., not just the order of magnitude) Big-Oh values for each of the following code samples, based on the number of statement executions. Your answers should be in the form of a Big-Oh polynomial (e.g., O(3N2 + 7N + 6)).

A)

for (int i = 0; i < n; i++)
{
    for (int j = i; j < n; j++)
    {
        sum += i;
    }
}

B)

for (int i = 0; i < n; i++)
{
    for (int j = 0; j < n; j++)
    {
        sum += i;
    }
}

C)

for (int i = 0; i < n; i++)
{
    sum += i;
}

for (int j = 0; j < n; j++)
{
    for (int k = 0; k < n; k++)
    {
        sum--;
    }
}

D)

for (int i = 0; i < n; i++)
{
    for (int j = i; j < n; j++)
    {
        for (int k = j; k < n; k++)
        {
            sum += j;
        }
    }
}

Explanation / Answer

A)

for (int i = 0; i < n; i++)
{
    for (int j = i; j < n; j++)
    {
        sum += i;
    }
}

for i=0, the j loop runs for n times(i.e 0 to n-1) so the statement is executed n times.

for i=1 the statement is executed (n-1) times.

for i=2, the statement is executed (n-2) times.

and so on upto 1.

hence the series becomes n+n-1+n-2+..................+1= n(n+1)/2 = (n2+n)/2 =O(n2/2+n/2).

B)

for (int i = 0; i < n; i++)
{
    for (int j = 0; j < n; j++)
    {
        sum += i;
    }
}

for each value of i in outer loop the statement inside the loop is executed n times.. So for n values of i the no. of statements executed is n*n = n2.= O(n2)

C)

for (int i = 0; i < n; i++)
{
    sum += i;
}

for (int j = 0; j < n; j++)
{
    for (int k = 0; k < n; k++)
    {
        sum--;
    }
}

here the statement in the first loop is executed for n times and the statement inside the 2nd loop is executed for n2 times like loop in (B)

hence the total execution is O(n+n2)

D)

for (int i = 0; i < n; i++)
{
    for (int j = i; j < n; j++)
    {
        for (int k = j; k < n; k++)
        {
            sum += j;
        }
    }
}

for i=0, for j=0, k loop runs for n times

for j=1, k loop runs for n-1 times

and so on up to 1.

for i=1, for j=1, k loop runs for n-1 times

for j=2, k loop runs for n-2 times.

and so on up to 1.

and so on.

so total no. of execution= n + n-1 + n-2+............+1

+n-1+n-2+..............+1

+n-2+n-3+.......+1

..................

+1

=((n+1)n)/2+(n(n-1))/2+.............+(2*1)/2

=1/2((n+1)n+n(n-1)+...........+2*1)

=1/2(n(n+1)(n+2)/3)

=1/6(n3+3n2+2n)

=O(n3/6+n2/2+n/3)

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.