Question

Determine

a) the output of each algorithm below

b) the number of assignment operations in each (show work)

c) the number of print operations in each (show work)

d) the complexity of each algorithm in terms of Big O notation (show work)

1.

Let n be a given positive integer, and let myList be a three-dimensional array with capacity n for each dimension.

for each index i from 1 to n do

{

for each index j from 1 to n do

{

for each index k from 1 to n do

{

​myList[ i ] [ j ] [ k ] = i;

Print the element at myList[ i ] [ j ] [ k ];

}

}

}

2.

Let n be a given positive integer, and let myList be a three-dimensional array with capacity n for each dimension.

for each index i from 1 to n do

{

for each index j from 1 to n/2 do

{

for each index k from 1 to n/2 do

{

​myList[ i ] [ j ] [ k ] = i;

Print the element at myList[ i ] [ j ] [ k ];

}

}

}

3.

Let n be a given positive integer, and let myList be a three-dimensional array with capacity n for each dimension.

for each index i from 1 to n do

{

for each index j from 1 to n/4 do

{

for each index k from 1 to n/4 do

{

​myList[ i ] [ j ] [ k ] = i;

Print the element at myList[ i ] [ j ] [ k ];

}

}

}

Answer 1

Solution of 1.

a) For the outermost loop i.e for each i , j varies from 1 to n and for each j , k varies from 1 to n,

Hence, the output will be

n² times 1 , n² times 2, n² times 3, ................. n² times n

b) Lets say n=2,the numbers present inside the 3d array will be -> 1,1,1,1,2,2,2,2 and the number of assignment operations = 8 = 2³

As we can say that for every element of the 3d array, one assignment operation is being performed.

Hence, total number of assignment operations = n³

c)

When j=1, Print operation will be performed n times i.e when k varies from 1 to n.

When j=2, Print operation will be performed n times i.e when k varies from 1 to n.

...........

When j=n, Print operation will be performed n times i.e when k varies from 1 to n.

Similarly the loop goes for i,

When i=1, Print operation will be performed n² times i.e when j varies from 1 to n and for every j, k varies from 1 to n.

When i=2, Print operation will be performed n² times i.e when j varies from 1 to n and for every j, k varies from 1 to n.

...........

When i=n, Print operation will be performed n² times i.e when j varies from 1 to n and for every j, k varies from 1 to n.

  

Hence, the number of Print operations = n*n*n = n³

)

d) As seen in the example mentioned in section c, the number of assignment operations = n³ and number of Print operations=n^3.

Since a single print statement and assignment operations take constant time to be done i.e time taken to perform both the operations i.e O(1) is constant and is independent from the number of elements in the 3d array,

Hence, the time complexity is solely dependent on the number of times the print and assignment operation has been done.

So, time complexity = n³ + n³ = 2n³ = O(n³)

Solution of 2.

a) n²/4 times 1 , n²/4  times 2, n²/4 times 3, ................. n²/4 times n.

b) As described in the section b of the above answer,

total number of assignment operations = n*n/2*n/2 = n³/4

c) As described in the section c of the above answer,

number of Print operations = n*n/2*n/2 = n³/4

d) With the same logic as discussed in section c of the above answer,

  time complexity = n³/4 + n³/4  = n³/2 = O(n³)

Solution of 3.

a) n²/16 times 1 , n²/16  times 2, n²/16 times 3, ................. n²/16 times n.

b) As described in the section b of the above answer,

total number of assignment operations = n*n/4*n/4 = n³/16

c) As described in the section c of the above answer,

number of Print operations = n*n/4*n/4 = n³/16

d) With the same logic as discussed in section c of the above answer,

  time complexity = n³/16 + n³/16 = n³/8 = O(n³)