Question

1. [Point: 10] The instance of a list ADT using array is L = (10, 20, 30, 40, 50, 60). Find the output of following code segment or what is returned by each statement.

remove(30);         

find(50):               

insert(7, 3):          

findKth(4)            

2. [Point: 5] The complexity of remove operation from a LIST ADT using array implementation is O(N). Explain why?
3. [Point: 10] Show that the running time for the following segment of code is O(N³) without using the rule for loop. Make sure to count each statement that takes one unit of time.

sum = 0;

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

for( j = 0; j < n; j++ )

            for( k = 0; k < n; k++ )

sum++;

Answer 1

Answer 1) :

remove(30) : it return the list array after removeing 30 .

[ 10, 20, 40, 50, 60]

find(50) : it return the position of 50 in array means 5.

insert(7, 3) : it return an array list after insert 7 at 3rd position.

[ 10, 20, 7, 30, 40, 50, 60]

findKth(4) : it return the value of 4th position in list array. means 40.

Answer 2) : The complexity of remove operation is O(n) because first it search the element in array list then delete this element, so, it will O(n).

For example : remove(30) : first it search the element 30 in array in O(n) time and delete the element in O(1) time and then shift the element of array in O(n) time. So, the total time is O(n)+O(1)+O(n) = O(n).

Answer 3) :

sum = 0;

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

for( j = 0; j < n; j++ )

            for( k = 0; k < n; k++ )

sum++;

Proof :

i = 0, j = 0, k = 0 to k = n (n times)

i = 0, j = 1, k = o to k =n (n times)

.

.

.

i = n, j = n, k = 0 to k = n (n times)

so, the sum++ statement will execute n^3 times . so the complexity = O(N^3).