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 the following code sample, based on the number of statement execution. Choose the answer that best agrees with the value you have determined. Keep the following considerations in mind:

    Remember to consider each statement in compound statements separately.

    Pay close attention to the initial and end values of loop variables!

    Loops such as "for" and "while" contain an implicit "jump" instruction that causes execution to proceed from the end of the loop back to the beginning of the loop.

Code sample:

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

Here are the answer choices:

O(N(N + 1) / 2)

O(4N2 + 5N + 2)

O(2N2 + 7N + 2)

O(3N^2 + 11N + 4)/2

O(N2)

Also, could you please include an explanation of how you arrived at your answer? Thank you.

Explanation / Answer

Answer:

for (int i = 0; i < n; i++) // Outer loop
{
    for (int j = i; j < n; j++) // Inner loop
    {
        sum += i;
    }
}

When i=0 in outer loop, the inner loop runs n times

When i=1 in outer loop, the inner loop runs (n-1) times

When i=2 in outer loop, the inner loop runs (n-2) times

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

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

When i=(n-2) in outer loop, the inner loop runs 2 times

When i=(n-1) in outer loop, the inner loop runs once

Adding 1+2+.........+(n-2)+(n-1)+n gives n*(n+1)/2

The Answer is O(N(N+1)/2)

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

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