Question

Determine

1. the output of the algorithm below
2. the number of assignment operations in each (show work)
3. the number of print operations in each (show work)
4. the complexity of each algorithm in terms of Big O notation (show work)

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 ];
}

}

}

can't provide anything else. This is the whole question

Answer 1

Let us solve each part one by one :

1. Output

The Output of given program will be

floor(n/4)*floor(n/4) times 1

floor(n/4)*floor(n/4) times 2

.

.

.

floor(n/4)*floor(n/4) times n

where floor(n) denotes largest integral number less than n. for example floor(2.5) = 2 .

If you take n = 10 in above code, the output will be :

1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9 9 9 10 10 10 10

Reason : As stated above output will be

floor(10/4)*floor(10/4) times 1 till floor(10/4)*floor(10/4) times 10

now floor(10/4)*floor(10/4) = 4 that's why numbers 1 to 10 comes 4 times each.

___________________________________________________________

2. Number of assignments

let x1 = Number of assignments (i=1)

let x2 = Number of assignments in increment of i (i=i+1)

let y1 = Number of assignments (j=1)

let y2 = Number of assignments in increment of j (j=j+1)

let z1 = Number of assignments (k=1)

let z2 = Number of assignments in increment of k (k=k+1)

let w1 = Number of assignments ( myList[i][j][k] = i )

Now, x1 = 1

x2 = n (i goes 1 to n)

y1 = n (depends on its outer loop)

y2 = n/4

z1 = n/4 (depends on its outer loop)

z2 = n/4

w = n * n/4 * n/4

So,total number of assignments = x1 + x2 + y1 + y2 + z1 + z2 + w = 1 + n + n + n/4 + n/4 + n/4 n* n/4 * n/4

= 1 + (11 * n) / 4 + n * n/4 * n/4

____________________________________________

3. Number of print statements

As i goes from 1 to n (n times)

j goes from 1 to n/4 (n/4 times)

k goes from 1 to n/4 (n/4 times)

So, print statement will run as many times nested loops runs that is : n * n/4 * n/4

________________________________________________

4. Time Complexity

Time complexity will be equal to Total Number of assignment statements + Total Number of print statements

that is 1+ 11*n/4 + n * n/4 * n/4 + n * n/4 * n/4

In terms of big O , complexity will be O(n * n/4 * n/4) or simply O(n * n * n)

_______________________________________________

Please comment below in case you have any doubt or anything is not clear.