(A) Consider the Following Algorithm Segment:
For$ i:=1 $ To$ n $

Question

(A) Consider the Following Algorithm Segment: 
For$ i:=1 $ To$ n $

Examlex · Accepted Answer

The Answer is a. Two multiplications and one addition are performed when the inner loop of the given
algorithm segment is executed for a total of three elementary operations for each iteration of
the inner loop. The number of iterations of the inner loop can be deduced from the following
table, which shows the values of i and j for which the inner loop is executed.
$a. Two multiplications and one addition are performed when the inner loop of the given algorithm segment is executed for a total of three elementary operations for each iteration of the inner loop. The number of iterations of the inner loop can be deduced from the following table, which shows the values of i and j for which the inner loop is executed. Therefore, by Theorem 5.2 .2 , the number of iterations of the inner loop is n + ( n - 1 ) + \cdots + 2 + 1 = \frac { n ( n + 1 ) } { 2 } The total number of elementary operations that must be performed when the algorithm is executed is the number performed during each iteration of the inner loop times the number of iterations of the inner loop: 3 \cdot \left( \frac { n ( n + 1 ) } { 2 } \right) = \frac { 3 } { 2 } n ^ { 2 } + \frac { 3 } { 2 } n . b. By the theorem on polynomial orders, \frac { 3 } { 2 } n ^ { 2 } + \frac { 3 } { 2 } n is \Theta \left( n ^ { 2 } \right) , and so the algorithm segment has order n ^ { 2 } .$
Therefore, by Theorem

5.2 .2

, the number of iterations of the inner loop is

n + ( n - 1 ) + \cdots + 2 + 1 = \frac { n ( n + 1 ) } { 2 }

The total number of elementary operations that must be performed when the algorithm is executed is the number performed during each iteration of the inner loop times the number of iterations of the inner loop:

3 \cdot \left( \frac { n ( n + 1 ) } { 2 } \right) = \frac { 3 } { 2 } n ^ { 2 } + \frac { 3 } { 2 } n .

b. By the theorem on polynomial orders,

\frac { 3 } { 2 } n ^ { 2 } + \frac { 3 } { 2 } n

is

\Theta \left( n ^ { 2 } \right)

, and so the algorithm segment has order

n ^ { 2 }

.

(A) Consider the Following Algorithm Segment:
For $i:=1$ To $n$

Definitions:

(A) Consider the Following Algorithm Segment: For i:=1 i:=1 i:=1 To n n n

Definitions:

(A) Consider the Following Algorithm Segment:
For $i:=1$ To $n$