Share
Explore BrainMass

Design and Analysis of Algorithms

Consider a table B that consists of m integers B [1], B [2] ... B [m]. Design an algorithm to produce a two-dimensional m x m table C such that each element C[i,j] for i <j contains the sum of the B [i] up to the B [j], that is, (B [i] + B [i +1] + ... + B [j]). The values C[i,j] for i >= j are left unspecified, that is, these can take any value.

a) Design an algorithm that creates the table C according to the above description and has time complexity Theta(m^3).
In response give either pseudocode or the description of the steps of the algorithm, and calculate the time complexity.

b) Design an algorithm that creates the table C according to the above description and has time complexity Theta(m^2).
In response give either pseudocode or the description of the steps of the algorithm, and justify the time complexity.

Attachments

Solution Preview

It is pretty detailed answer, so please go through it thoroughly and patiently.

I am not giving a cooked response but instead providing enough guidance in form of number of times each step executes in the presented algorithms which should help you put together the final answer for time complexity of respective algorithms.

When we talk about execution of a for-loop, if the for-loop-body executes m times, then the for-loop-condition-test executes (m+1) times - m times for success (that is, executing the loop-body) and once for failure (coming out of loop). For sake of simplicity in this discussion, I am not making distinction between the number of times the loop-condition executes and the number of time the loop-body executes, and instead consider the number of times for-loop executes as the number of times the for-loop-body executes.

(a)
S1: for i = 1 to m // Go over each row of matrix C.
S2: for j = 1 to m // Go over each column of matrix C.
// Compute C[i,j] as per the given description for computing C[i,j].
S3: if (i < j) // Otherwise C[i,j] is left unspecified.
S4: sum_itoj = 0
S5: for k = i to j
S6: sum_itoj += B[k]
S7: endfor
S8: C[i,j] = sum_itoj
S9: endif
S10: endfor
S11: endfor

In the above logic, the statement

for i = l to u

means same as

for (i=l; i <= u; i++)

when expressed in a programming language like C/C++/Java etc..

Body of for-loop in S1, that is, S2-S10, will execute m times.

Body of for-loop in S2, that is, S3-S9, will execute m*m times; as for-loop in S2 executes m times in itself, and the entire for-loop-block S2-S10 will execute once for each iteration of outer for-loop in S1.

If-statement in S3 will execute m*m times (for each iteration of for-loop in S2).
However the if-body comprising of S4-S8 will ...

Solution Summary

Solution explains in detail how the algorithms take shape in this case, but for the time complexity computation part it does not give a cooked response. Instead it provides enough guidance in form of number of times each step executes in the presented algorithms which should help you put together the final answer for time complexity of the respective algorithms.

$2.19