You are given the following program fragment Indicate beside

You are given the following program fragment. Indicate beside each statement the cost in terms of problem size and determing T(n), the total cost. Then derive the Big Oh complexity.

void Sum1( i n t n )

{

sum1 = 0;

for( i =1; i<=n ; i++) {

f o r ( j =1; j<=n / 2; j++) {

sum1++;

}

}

f o r ( i =1; i <=1000000; i++) sum1++;

}

T(n) =

Solution

void Sum1( i n t n )

{

sum1 = 0; constant time c1

for( i =1; i<=n ; i++) { n times

f o r ( j =1; j<=n / 2; j++) { n/2 times

sum1++; constant time c2

}

}

f o r ( i =1; i <=1000000; i++) sum1++; constant time c3

}

T(n) = c1 + n*(n/2) *c2+ c3

= a + b(n^2) where a and b are constants

As n grows larger constants can be ignored so

T(n) = O(n^2)