Question

1. Write down an algorithm in pseudo-code whose running time where input is an array whose length defines the problem size. Take the cost of execution of each line of the algorithm as 1.

2. Make comment about the following paragraph:

“You are given two independent algorithms and whose running time complexities are and , respectively. If we add a new line to our algorithm in which it calls the algorithm then the running time complexity of the modified algorithm becomes ”.

Answer 1

Part a)

A pseudo code algorithm whose running time is the length of an input array.

For this time complexity, we can consider an algorithm to print the elements of the input array. We will traverse the array of given size. Each element of the array will be visited once and printed. The algorithm is as follows:

ALGORITHM: print-array (A)

BEGIN: n = A.length()

for i=0 to n-1

print( A[i] )

END;

Since we visit each element of array only once and length of array is 'n', we get the time complexity of the algorithm to be O(n) ie. the array length.

Part b)

If we are given two independent algorithms with time complexities t1 and t2 respectively, and we add a new line to our first algorithm to call the second algorithm, then the total running time complexity of the modified algorithm will be t1 + t2.

Before jumping to the second algorithm, our first algorithm will execute for time complexity of t1. On jumping to the second algorithm, a further time of t2 will be taken to execute it. Thus, the total time complexity of the modified algorithm will be t1 + t2.