1 Determine the running times predicted by the detailed mode

1.            Determine the running times predicted by the detailed model of the computer for the following program fragments:

Int   Sum (int x, int n)

{

                int sum = 0;

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

                  sum = sum *x +1;

             return sum;

}

2.            Repeating question 2, using the simplified model of the computer.

Solution

1.) Using detailed model of the computer let\'s have a look at time complexity of each line.

int sum = 0; this is assignment operation. which will be done only once so the complexity is constant time, which is O(1)

the loop is running for n number of times performing multiplication and an addition operation along with an assignment operation which will take constant time means O(1) time but n number of times so the time complexity will be O(n) time.

So, overall complexity of the program will be O(n) time.

2.)

Using simplified model

running time of the given program is T(n)=T(n)+c

After calculating the time complexity will be n*c=O(n) time.