Ex.

for ( int i = 5; i < n; i++ )

Sum++;

Most precise answer:

Running time O(n)

Explanation: There is a single loop that runs n-5 times. Each time the loop runs it executes 1

instruction in the loop header and 1 instruction in the loop header and 1 instruction in the body of

the loop. The total number of instructions is 2*(n-5) + 1 (for the last loop check) = 2n-9 = O(n).

A slightly less precise but still acceptable for full credit answer:

Running time: O(n).

Explanation: There is a single loop that runs n-5 times. Each time the loop runs it executes 1

instruction, so the total number of instructions executed is 1* (n5) = O(n) (also OK: ?(n)).

1. for ( int i = 0; i < n; i+=2 )

Sum++;

2. for ( int i = 1; i < n; i*=2 )

Sum++

3. for ( int i = 0; i < n; i++ )

for ( int j = 0; j < n; j++ )

Sum++;

Running time: O(n^2)

4. for ( int i = 0; i < n; i++ )

sum++

for ( int j = 0; j < n; j++ )

sum++

// The above are two loops one after the other, NOT nested

5. for ( int i = 0; i < 2*n; i++ )

Sum++

6. for ( int i = 0; i < n*n; i++ )

Sum++;

7. for ( int i = 0; i < n; i++ )

for ( int j = 0; j < n*n; j++ )

Sum++;

8. for ( int i = 0; i < n; i++ )

for ( int j = 0; j < 10000; j++ )

sum++;