Question

Determine

1. the output of each 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)

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

}

}

Answer 1

Output determination:-

1 will get printed (n/2)*(n/2)

2 will get printed (n/2)*(n/2)

3 will get printed (n/2)*(n/2)

.

.

.

n will get printed (n/2)*(n/2)

So we can say each iteration or vakue of i get executed (n/2)*(n/2) times

As we n/2 is approximately equal to logn

So the time complexity is here

O(nlognlogn)